Eu escrevi um programa em python , que demorou menos de 24s para mais de 27500 arquivos:

https://github.com/jbsilva/renamer

O seguinte comando cria 20 diretórios e 80 arquivos para testes:

julio@julio-acer /teste> mkdir -p pasta{1,2}' '{4,5}/pasta{6,7}' '{8,9} && touch pasta{1,2}' '{4,5}/arquivo{1,2}' '-' '{3,4}.txt pasta{1,2}' '{4,5}/pasta{6,7}' '{8,9}/arquivo{5,6}' '-' '{7,8}.txt