MediaCoder!! A bit complex to use....but very very powerful....can use all 8 cores of your chip.
Plus, its totatly free !!
PS:- MP4 is only a container format....compressed video quality will depend on which codec you use. For example, the H264/AVC codec can give you the same quality as older DivX\XviD formats, but at just half the file size. Both can be packaged inside an .mp4 container.
I think your current software is trying to encode with the XviD codec. IIRC that codec is not highly multi-threaded. Try switching to H264/AVC and see if it speeds up.