Yes indeed all modern video codecs are based on encoding differences between key frames. GIF has the most basic implementation of that (it can update only a window in the image instead of the whole image).

The original GIF can actually be compressed losslessly down to just 1.4MB with a better compressor like https://gifcompressor.com .

MP4 (and similar codecs) are not typically very good at compressing regions of constant colour, while GIF is very good at that. However I have to admit that the output of that converter is acceptable in MP4, better than I would have expected (though noticeably worse quality).

BTW curiously (likely to better performance on regions of constant colour) the non-lossy WebP does better on this example coming in at just 1.2MB!