What version of Premiere Elements are you using and on what computer operating system is it running?
What is the player that you are using?
For now, I will assume that you are using Premiere Elements 11, 12, or 13 on Windows 7, 8, or 8.1 64 bit.
What are the properties of what you are putting on the project's Timeline?
And, what are your project settings?
The basic idea is to set up the project settings (you manually or the project automatically) to match your source properties.
After the editing phase and you are ready to export to a file saved to the computer hard drive, you go to Publish+Share/
Computer/ and make your choice. There is more than you can see for Computer choices. You use the thin scroll bar
to the right of the choices to scroll down to see the whole list.
If you want an export with a .mp4 file extension, then you should be looking at
with one of the MP4 presets described with the properties comparable to your source.
You can also find an .mp4 export under
Mobile Phones and Players
If you obtained a file with a .mpg file extension, I am guessing that you got as far as what you could see, that is, Publish+Share/Computer/MPEG.
Lots of possibilities...but keep in mind that .mp4 is just a file extension (container/wrapper format that wraps the important video and audio compressions).
So, we can discuss that further.