If I understand everything correctly, this demo uses 16-bit 32x32 tiles for rendering. 16-bit tiles could be replaced with 4-bit tiles with individual palettes, reducing the memory load approximately 4 times. 16 colors actually should be enough, considering that the size of each tile is only 32x32 pixels. With a proper palette generation algorithm, everything should look fine. As I remember, pngquant even had an option to quantize colors to RGB555, which should provide a good palette within N64 rendering limits.
If I understand everything correctly, this demo uses 16-bit 32x32 tiles for rendering. 16-bit tiles could be replaced with 4-bit tiles with individual palettes, reducing the memory load approximately 4 times. 16 colors actually should be enough, considering that the size of each tile is only 32x32 pixels. With a proper palette generation algorithm, everything should look fine. As I remember, pngquant even had an option to quantize colors to RGB555, which should provide a good palette within N64 rendering limits.