Você poderia usar a expansão de shell em vez de globbing:
for file in lesson{1..10}.mp4;do
read line
mv -v "${file}" "${line}"
done < rename.txt
Embora isso pareça bastante propenso a erros, se você tiver muitos arquivos, precisará compará-los com o número no início da linha do arquivo renomeado. Algo como:
for file in *.mp4;do
num=$(echo "${file}" | sed -E 's/^lesson([0-9]+).mp4$//')
line=$(grep -E "^ *${num}\." rename.txt)
mv -v "${file}" "${line}"
done
Desta forma, não importa qual a ordem em que o arquivo rename.txt
está, e não importa qual ordem o shell coloca nos nomes dos arquivos.