Tente:
find -iname "*.txt" -exec sh -c 'for f do basename -- "$f" .txt;done' sh {} +
Seu primeiro comando falhou porque $(...) é executado em subshell, que trata {} como literal. então basename {} .txt return {} , seu find se tornou:
find . -iname "*.txt" -exec echo {} \;
qual o nome do arquivo de impressão correspondente.