How to put 2 or more fifos into 1 M9K in C3 device

Synchronous or asynchronous?

A FIFO requires two independent address ports, so two FIFOs requires four addresses. The M9K only has two. So there is no easy way. You could timeshare a memory block, running it at 2x the speed and therefore doing twice as many reads/writes per clock. You would have to use your own FIFO or hack the megafunction(which is probably AHDL) and hence not very easy. You could build one of the FIFOs out of logic elements, but that's quickly inefficient and I'm assuming you thought of that and ruled it out.