emumovies has an option to convert them as they're downloaded. I don't remember if it has an option to convert them afterward, but it might.
That said, the latest beta version of Mala supports mp4. (v1.745)
http://www.malafe.net/index.php?page=downloadI'm using the mp4 files from emumovies with it.
If you're using v1.745 and it doesn't work, try a different codec pack.
I can't remember which one exactly. I installed the k-lite pack with the old version of Mala, but I remember installing ffdshow for some reason also.