You could get external RAM for the Mega2560, still might. That would give you 56K heap space.
Try multiplying 128 x 128 x desired color depth to see how real storing that in RAM will be.
Smart move is buffering 128 x color depth bits image strips stored in flash (2560 has 256K flash, little room?) or SD and writing pictures a strip at a time. If it takes 40ms, human eyes can't follow 25FPS.