They're not dealing with such large directories, but here are a couple threads that might be relevant:

• Fastest way to recurse through VERY LARGE directory tree
• Efficient processing of large directory

I wonder if the best first step might be something like this on the command line:

for i in {a..z}
    do mkdir $i
    mv $i* $i/
done
[download]