How to make very compact code

I assume you're using alt_main() instead of main(). If you're not using any standard library stuff, that should link out, too. Also, you can do your own initialization instead of alt_sys_init().

Another thing you can do is get rid of interrupts and just poll everything. More CPU use, and it's not as fast, but it's a lot simpler to debug.

I've got a system with a 32 MHz Nios II/e using 2K of ROM and 512 bytes of RAM on-chip, and nothing external. It shares a Cyclone 1C3 with some DMA and FIFO stuff. It took some work, and there's a _mulsi3() routine that refuses to go away (even though it's not referenced at all).

I think there's a flag you can pass to nios2-elf-nm when you run it on your final elf file so that it shows you how much space each object in the file takes. That can at least help you see where yourr memory is going.