I don't have a ready answer, but if I were confronting the same question, I'd run a smaller mock-up (with 1000 keys, say), and figure out a multiplier based on that.

Actually, more truthfully/realistically, I'd probably just go with the naive approach, and if I discovered that I'm in deep doodoo (in the form of a script that slows down to a crawl), I'd think harder about it.

With something in the range you're dealing with, I've often found myself needing to use tied hashes, just to keep Perl from spending 95% of the time swapping.