FOG Format Reference (REWiki)
The name says it all! Easy concept, hard to explain: The game has 16 "fog steps". These fog steps are pre-calculated for all 256 colors in the palette, using only colors from the same palette. It tries to find colors in the palette which match a blending between the real color and the fog color as close as possible. This is more an index-remapping than a fog effect. At step 16 all 256 colors have the same index: the fog color. Maybe this image shows the concept:
The poor appearance of the blending is no error or compression artifact. It is the correct representation of the FOG file. Because everything is 8-bit, it's impossible to blend smoothly between all colors. FOG files are 4096 bytes long.