Graphics hardware interaction is always tricky, VGA palette data is basically written to an internal hardware port as a serialized stream, one byte for each color channel. VGA uses a 256 color palette with 18 bits per color. Tracing this kind of thing is pretty difficult (ie nightmarish), unlike file IO which is comparatively trivial.
I had no idea how to figure out the palette, until I remembered that I'm not running the game on real hardware but through Dosbox. So I just found the function in the dosbox VGA emulation layer that deals with the palette stream, changed it so it outputs a nicely formatted line for each palette update from the game, and just played the game for a little bit. Now I have a text file with stuff like this:
mColorTable[79] = qRgb(134, 0, 186); // 21 0 2e
mColorTable[80] = qRgb(255, 162, 101); // 3f 28 19
mColorTable[81] = qRgb(85, 85, 85); // 15 15 15
mColorTable[82] = qRgb(56, 56, 56); // e e e
mColorTable[83] = qRgb(36, 36, 36); // 9 9 9
mColorTable[84] = qRgb(0, 0, 0); // 0 0 0
mColorTable[85] = qRgb(138, 0, 0); // 22 0 0
mColorTable[86] = qRgb(162, 0, 0); // 28 0 0
mColorTable[87] = qRgb(186, 0, 0); // 2e 0 0
With a proper palette I've learned a bit of how the game deals with colors, at least for characters.
There are 3 custom blocks of 16 colors that are reserved for enemies/critters. These are index 32-47, 48-63 and 64-79. This puts a limit on how many different critters there can be in a single battle.
The file ENEMYPAL.DAT contains sets of custom colors that critters can use. Each entry is 53 bytes long, 71 entries in total. The first byte tells the first index of the 16 colors. It's either 0x60, 0x90 or 0xC0, divide by 3 and you get 32, 48 and 64 in base10. The next 48 bytes are byte triplets for 16 colors. The last 4 bytes I have no clue about, so they're probably vitally important.
The first 6 entries are for the city guard sargeants, the next 6 for the regular city guards. No idea about the rest. I guess trial and error is the only way unless someone else can find a pattern.
For player characters it's completely different. They have 8 customizable colors each, but their sprite files all use the same color indices for them, 235-242. Basically the game replaces occurences of these indices in the hero sprites with other indices "owned" by each character slot. Slot A gets index 80-87, slot B 88-95, slot C 96-103, slot D 104-111, slot E 112-119 (if used). Seems kind of silly they went to all this trouble just for a nearly useless feature.