Eu sempre trabalho com a regra de ir até um máximo de ~ 1000 com ext2 / ext3. Eu suspeito que a escolha do sistema de arquivos possa afetar sua escolha.
O limite absoluto em ext3 é ~ 32k. Dê uma olhada em todos os detalhes da Wikipédia: link
Em termos de um algoritmo de hashing para seus diretórios, eu recomendo usar o último dígito do id. Se você calcular $id % 10
e usar esse valor, isso funcionará como um tratamento. Dessa forma, você obtém uma distribuição uniforme.