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

I've run into what I think is similar behavior. I have some CDs that have something like 11,000 files on them, all in a single directory. On a Windows or MacOS 9 box, I saw excruciatingly slow access times for files down in the list. The first few hundred were plenty zippy, but the farther I got into the list, the slower the access.

Doing the same access on a Solaris box or MacOSX yielded pleasantly surprising results. File lookups were more like constant time instead of proportional to how far into the list the name was.

I suspect that the problem is exacerbated by using a "slow" medium, like CD-ROM or network volumes.

yours,
Michael