Tente isto:
find /source/directory -name "*.pdf" -exec \
sh -c 'convert -thumbnail x80 {} $(dirname {})/thumb_$(basename {})' \;
Eu tive que modificá-lo levemente para:
find /source/directory -name "*.pdf" -exec \
sh -c 'convert -thumbnail x80 {} $(dirname {})/thumb_$(basename {} .pdf)'.png \;
Para ter o nome da base, limpe a extensão de arquivo e, em seguida, anexe .png.
Obrigado a todas as respostas. Este trabalhou bem para mim!