Your problem is most likely not really related to perl, it is a filesystem thing, where lookups are made in linear time with regards to the number of files in a directory.
You should look into the htree option of ext{2,3}. Goggle will help you there ;)