Part of your slowdown may come from the repeated reallocation of the base data structure for the hash. There's an array in there that holds the elements of the hash--when it's full, perl has to allocate a new, larger chunk and copy the data from the old chunk to the new one. (This also tends to frag memory) You can use keys in an lvalue context (keys %foo = 1000000) to presize the hash, which may help some.

Depending on how well your keys hash out, you may find you're badly overloading one of the buckets in the hash structure as well. While perl tries to make sure the keys are evenly distributed by the hashing function, it doesn't always succeed, and in that case there's not a whole lot you can do. Printing the hash in scalar context will give you a little bit of info about that--if you see the two numbers returned are wildly different, you've got a badly mis-balanced hash. (In which case you're kinda out of luck)