I don't know if this is feasible in your situation, but you could do something to make it easier for the OS by rearranging your files.

The simplest way to explain it is to put all of the files in sub-directories whose name is the first letter of the original file. So A* gets moved to ./A, and so forth. If you want to go to a second level, you can do that too.

Rewrite your script to use this structure and you will see a performance improvement.

CPAN's directory structure follows this strategy, as does Yahoo, in some parts of its service.