This is more of a comment than an answer but it's too long for a comment box and I hope to extend it as I learn more.
My first thought was that the negative value might be preventing some optimization so I looked for a counterexample and found something surprising:
Table[
With[{a = RandomInteger[{1, 100000}, 1000000 + x]},
First @ Timing @ Do[Tally[a], {10}] / 10
],
{x, -5000, 5000, 1000}
]
{0.121681, 0.117001, 0.113881, 0.115441, 0.118561, 0.00468003, 0.00468003,
0.00468003, 0.00312002, 0.00468003, 0.00468003}
It seems that Tally
invokes an optimization on (some) packed lists of integers over length 1×10^6 and this optimization has been present since at least version 7. This seems similar to things like "ArrayCompileLength"
but I cannot find a System Option that applies. At least on the given example the crossover point seems poorly chosen as there is 40X speed-up indicating that an earlier point would have been better.
Since we do not know the details of this or other optimizations used by Tally
I can only presume, but it seems plausible that the presence of a negative value causes the heuristic to trigger only on a slightly longer list. (1000010
is sufficient for both timings to be similar.)