For a typical users use case, I bet you could downscale the image 16x (using the GPU, and therefore very fast), flood fill on the much smaller image (using slow javascript over each pixel), then expand the image up to the original size and reprocess just the border pixels (and there aren't many border pixels compared to the total filled area).

This method might not produce perfect results when the paint can 'escape' through a tiny gap that isn't visible on the downscaled version... But at the same time, I suspect most users don't actually want the paint to escape through a tiny gap, so that might be the right behaviour.