DSLinux absolutely runs in 4 MB (i.e. w/o a RAM expansion pack), it's just going to take a bit of work to also fit the web server + whatever CGI they wanted without a pack.
The EZ-Flash V 3-in-1 actually added a whopping +16 MB (128 Mb) of PSRAM! Growing up I only ever had the +8 MB pack from Opera... what a weird bit of history that browser port was :).
I wouldn't say uClinux was any less Linux, over time its features even merged to mainline in the 2.x series, including the ability to run MMU-less in version 2.5.46 https://lwn.net/Articles/14823/
The EZ-Flash V 3-in-1 also had either 64 MB or 128 MB of NOR flash (depending on the revision) in addition to the 16 MB of PSRAM. There was also some battery backed SRAM for save data.
Can it run Linux? Ehhh....... can it run a web server? Absolutely.
* we don't talk about using the 0.6MB VRAM for purposes other than video (even though it should work fine).