Apparently [1] MP4s (at least their file sizes) can be optimized much more than animated GIFs, although it doesn't seem like that's been fully done here.

[1] http://gfycat.com/about