Seu script atual usa apenas um valor decimal - isso obviamente se traduz no valor sem zeros iniciais.
Você teria que preencher a string com o comprimento de 4 caracteres, com zeros à esquerda. Você faz isso usando backticks ''
para obter o resultado da chamada printf printf %04d $j
.
Como resultado, você deve ter o comando completo:
for i in *.jpg; do let j+=1; mkdir 'printf %04d $j'; done
Fonte: StackOverflow: bash - Preenchendo zeros em uma string
(Obviamente, veja também as respostas adicionais para essa pergunta, se você quiser uma solução mais profunda, mas isso definitivamente funciona perfeitamente para este caso de uso.)