Para convertir videos de mkv a mp4 en GNU Linux es súper fácil, puedes utilizar la herramienta ffmpeg desde una Terminal de la siguiente forma. Debes sustituir los nombres archivo-origen.mkv y archivo-destino.mp4 segun sea tu caso. Si quieres hacer lo inverso, es decir convertir de mp4 a mkv ejecuta ffmpeg de la siguiente forma.