Você precisa ativar a globalização recursiva no Bash:
shopt -s globstar
Em seguida, um loop simples, substituindo o nome do arquivo de saída:
for f in **/*.mkv; do avconv -i "$f" -c copy "${f%.mkv}.mp4"; done
Observe que isso pode falhar em vídeos que contenham codecs que os contêineres MP4 não podem manipular. O MP4 é mais restritivo que o MKV, que basicamente pode incluir todos os codecs.