While we don't store as many images as you are talking about (usually around the 20K+ mark), we have 12TB of info that we deal with on a regular basis. Our scheme for keeping track of these images is splitting accross the different archives (RAID partitions) which are used as seperate directories, all linked to one central directory. From there we give each separate image a unique 10 character image code and use that as the name of the sub-directory. The image is then stored within that sub-directory. All of this is kept track of in an Oracle database.
In the *nix world it would look something like this:
Now this is a very simplified version of how our archive is set up, but it does work fairly well. I think that the major player here is the database keeping everything straight. The previous solutions using the 10K per archive sounds like a good cutoff point to me, also. I know using to many image sub-directories will probably cause you problems.
I know that this is not a Perl solution, but maybe it helps in some little way.