Warning: non-perl solution ahead! ;-)

If you're on Linux you may want to go for a ReiserFS partition. ReiserFS uses binary trees to index directories and is still VERY fast on directories holding hundreds of thousands of files.

It may take a while for a simple 'ls' to complete though, because ls sorts alphabetically.