En linux (probado en Ubuntu) para convertir de MKV a MP4 manteniendo el formato de los subtítulos incrustados en el mismo vídeo, se puede realizar ejecutando un único comando:

Primero instalamos "mencoder", es un complemento de MPlayer:

sudo apt-get install mencoder
Después ejecutaremos el siguiente comando, cambiando "VIDEO" por el nombre del fichero:

mencoder VIDEO.mkv -slang eng -ass -embeddedfonts -o VIDEO.mp4 -oac faac -ovc x264
Tendremos el vídeo convertido a MP4, la pega es que no coge el opening y el ending si están separados.