Even though it's not showing up in the gallery, are you able to play the video on your phone at all?
If you're not able to play the video(s) in question, it's possible that they were encoded with a codec that's not supported by your phone. MP4, like any other file extension, is basically just a container that the file sits in. How the specifics of the actual information in that container were made (which is where the codec comes in for video) can vary. Not all .mp4 files are the same.
While it won't solve the problem of the video not showing up in the gallery (only re-encoding the video will do that), you might want to think about downloading a different video player from the Play Store that supports a wide range of codecs. This will allow you to be able to play the videos on your phone.
MX Player is one of my favorites, and it has played pretty much any video format I've thrown at it. VLC is the standard go-to program on computers for me and for many people, and
their Android app is currently available (but in beta).