Further pursuing the idea of running MegaZeux on the DS, I wrote a routine to render 8x14 character textmode to one of the screens. I managed to get 52 FPS on my first try, which could be good enough. MegaZeux is low motion enough that probably less than 20 FPS would be acceptable.
The reason why it's not straightforward to scale down a 640x350 textmode screen is that the DS limits the size of an "extended rotation background" (one with per-pixel addressing) to 512x512 pixels. My solution was to plot one pixel horizontally for every two pixels in the current character, squeezing the screen down to 320x350. I can use a simple map from the two-pixel bitmap to the one-pixel result:
That just leaves me with the problem of calculating a 50/50 blend for many of the pixels. As luck would have it, the MZX palette is 16 colors but the NDS palette is 256 colors—more than enough to precalculate a blend for every color. And it's EXACTLY enough to do it naïvely: result = 16*color1 + color2.
It turns out that this method runs very well on the hardware. I was expecting 1/10 of the speed that I got. Add in some hardware scaling enhancement tricks, and the result is not bad looking. Characters are squished to about 3x7 pixels, which makes text reading a challenge, but not impossible. For real game playing, I'd probably ape ScummVM and have both a zoomed-out and a zoomed-in screen. The zoomed-in screen could be accomplished using sprites at 1:1.
There are a few caveats to this method. The zoomed screen uses 256K of VRAM, which are both of your 128K main screen banks if you want to use 128K extended rotation and sprite banks on the subscreen. The zoomed screen can't run on the subscreen at all. There are also some "checkerboarding" artifacts visible. If you've ever taken a screenshot of a ZZT or MZX game and scaled it down with a poor quality scaler, you've seen this before. But I'm pretty sure abandoning the hardware scaler completely would destroy the performance.
I am pleased :)