Compressing videos create even larger file
As @pram said above in the comment, mp4 videos are already compressed, and other video formats probably also use compression to some extent. Therefore, trying to compress them won't result in little (if any) reduction in size (this also applies, at least in part, to pictures and music). In this case, it looks like the metadata (for the compressed file itself) might be causing the increase. The only compression format that might (and that's a strong might) result in some reduction is xz.
On another note, if you want to reduce the size of those videos, look instead into re-encoding the videos using something like Handbrake.
Really, the fact that the files are already compressed is not the crucial problem. It's this: compression in general can only work if the data has some kind of redundancy in it. That's practically always the case for uncompressed files – however, it's not necessarily obvious what the redundancy is. General-purpose compression algorithms mostly target the kind of thing obvious in text files: many words turn up not just once but plenty of times in identical form, perhaps phrases of words can be combined, etc. etc.. The algorithms are quite good in generalising this to anything from ASCII-encoded phone number lists over chinese poetry to binary machine code, but they can't possibly work for any kind of data. In particular, media files are conceptually analogue data, in a noisy digital representation. That means, there's not really any of the kind of textfile-reduncancy at all: some motives might be recurring, but always with a slightly different configuration of sensor noise. That's why all compressed image/AV formats use some cleverly chosen transformation as their first encoding step, normally based on DCT or wavelets. These transformations roughly speaking move the picture-portions and noise-portions into different locations, so they can well be seperated and with lossy compression you retain only the information you think is most "important", which does not include the noise, while the "good information" has lots of redundancy. (That's not really how it works, but sort of.)
If general-purpose compressors used these transformations, the effect would be the opposite: most digital information would actually be misclassified as some kind of noise, because it lacks the "smooth" structure you find in analogue signals. And after lossy video compression obviously neither analogue smoothness or digital recurrence can be found anymore (if it were, the codecs would use another bzip-stage or something themselves!)
The reason you're having no luck is that mp4 is already compressed, you can't compress it further. All you are doing is adding the compression format's header information to the file.
Since the files are already compressed and you can't compress them further, this results in an increase in file size since all you're doing is keeping the same information and adding a few more bytes of header info.
This is a nice example of the pigeonhole principle.
Since the file is already (lossy) compressed, there's little to no reduction to be had anywhere, which means that you're already at zero net gain. As the others mentioned, the compressed format itself has a certain, usually negligible loss in in its own meta-data. All of this comes together means that there is probably no pigeonhole left in the set of equal or smaller files and thus your compressed data falls into the set of larger files.