Primeiro, crie arquivos com os nomes de arquivo para cada arquivo:
find <directory> | split -l 5000 - files.
Em seguida, crie os tars:
for f in files.*; do tar -cf $f.tar --files-from $f; done
Não testado, mas a ideia básica deve funcionar.