uniq is a POSIX utility. You used uniq -c and it works like this:
The
uniqutility shall read an input file comparing adjacent lines, and write one copy of each input line on the output. The second and succeeding copies of repeated adjacent input lines shall not be written. The trailing of each line in the input shall be ignored when doing comparisons.
Repeated lines in the input shall not be detected if they are not adjacent.
[…]
-c
Precede each output line with a count of the number of times the line occurred in the input.
(source, emphasis mine)
This means that non-adjacent lines are treated as if they were different. In your use case you need to sort first to make identical lines adjacent. Only then uniq will do what you want.