Okay. Four palettes fits, at least these four I'm using to test. It uses 125 out of 128 macrocells, but it fits. That's pushing it -- it's impossible to predict if the final palettes will fit. I might need a 256 macrocell device.
@elfi Right now, I'm trying a build with 15 colour output pins instead of 18 -- that might make the difference, as it's a >75% reduction in theoretical possible colours.
@elfi Couldn't say without trying.