Makes me wonder if this could be even faster, if you cheated and just generated copies of the masks already colored, for every color available. From looking at the video, I see you have 10-11 colors available at any given moment with possibility of changing them to, presumably, arbitrary RGB value. That means you only need to keep 11 color variants of each mask, which should still fit in RAM. You also need to be able to replace a single group of masks with a new set of masks faster than the user can switch colors in the custom color picker.
(I know, it's a dumb idea in this case; I'm posting it as a reminder to both myself and everyone else, that many problems can be solved by checking or caching every possible state.)
Sure, but at any given moment, they can use only ~12 of them (+ the rainbow thing, now that I played a bit and know how it works). Meaning, you can keep 12 pre-filled variants of each mask, one for each color on the main palette, and recolor all masks of a given color when the user picks a new one from the top-left color picker. I bet you can do this update faster than they can dismiss the color picker and tap on the canvas.
I see you have drawing tools there as well, but they seem to be ignored by flood filling (e.g. if I draw a closed circular border myself and use flood-fill on the empty centre, the fill will just paint over my circle border and continue filling to the boundaries of the initial region of the original image) - so they don't even make a counterpoint I was worrying they would.
(I know, it's a dumb idea in this case; I'm posting it as a reminder to both myself and everyone else, that many problems can be solved by checking or caching every possible state.)