I was thinking about your post. I updated my last reply.
If you are using Linux Mint version 18, then I would upgrade that to version 18.1 through the Mint Update Manager.
Can you give us an example of what the videos mp4 format resolution is now that you are working with? I'm not sure that it matters, but your older video player might not be able to handle widescreen (aspect 16:9) video formats either, so when testing the conversions, try non-widescreen formats (aspect 4:3, sometimes called "full screen") too.
As an ex-software developer, I test a lot of software applications and utilities for Linux Mint members and for my own curiosity and use. You might consider creating sub-folders underneath your "/Videos" folder for the various multi-media converter (transcoder) application's output, and trying each one out to find out which one does what you want and that you like the most. You could create folders for "Avidemux", "Curlew", "FFMultiConverter" (ffmc), "WinFF", "Handbrake", "Transmageddon", etc... Then, try converting one video into various ".avi" formats that have a resolution of 720p or less to see which format works with your media player. Once you have found one that works, then you can use one of the applications to convert the rest of the videos.
I have personally tried most of the various multimedia converters. Their speed depends upon the size of the video(s), the application, and your computer hardware, most have settings for "multiple threads" to take advantage of multi-core CPU computers, like yours. The applications have "presets" that you can choose from, or edit, to control the output of the new video file, like to convert to ".avi" and at the same time, scale it into different sizes (video resolutions), like 720p or 480p, etc... The usual default output of "Avi" will keep the same size video, but if you select advanced options, video tab, video size, then you can change that, and the aspect ratio (widescreen vs fullscreen); the presets are already configured for these options, and using the advanced option will let you see what settings the "preset" is using.
Most of the multi-converters can process more than one video at a time. To convert a 1280x720 HD video (42min long) averaged around 16-30 minutes on my older computer hardware. Your times will vary.
My favorite multi-media converters (transcoders) that can output "avi" video files are "Curlew" and "FF Multi Converter" and they have a few "presets" for various "avi" output, and process multiple videos at one time.
Avidemux is great for many uses, but I do not think it can do multiple videos at one time.
Avidemux has an "appimage" method of being installed and run which I recommend. You must have "fuse" installed from the Software Manager or Synaptic Package Manager (SPM).
What is an “AppImage”? How do I install it?https://askubuntu.com/questions/774490/what-is-an-appimage-how-do-i-install-it
Avidemux AppImage (SourceForge)https://sourceforge.net/projects/avidemux/
Avidemux AppImage (FossHub)
- Download Avidemux Universal linux binary - 38.13 MB version: 2.6.20 https://www.fosshub.com/Avidemux.html
Hope this helps ...