You are referring to NAT routers. Normal routers (not implementing NAT) require only very little amounts of memory and processing power for routing - they are essentially stateless and pretty much all they require is bandwidth. (Internet routers may require significant amounts of memory and processing capabilities for their routing table, but that's another story.)
NAT routers translate one address scheme to another - usually private to public IP addresses or vice versa. They need to read and update their translation table where each connection is tracked. That table is in memory, memory is limited, so the NAT table's size - the maximum number of connections that can be managed - is generally limited.
If the NAT table gets filled up, the router needs to resort to some sort of contingency: unless it drops older connections it cannot accept new ones. If low memory conditions aren't handled well by the router firmware, the device might even crash or hang (sadly quite common for consumer-grade routers).
Simply adding more memory to a small hardware model might backfire when the CPU can't adequately handle the larger NAT table any more - you'd likely want processing being done in finite time. So, more memory also requires either a faster CPU or increased hardware performance when NAT is done in hardware.
NAT routers exist in various sizes. The most reasonable solution would be to get a router that can handle the number of planned connections (number of users * average number of connections per user). A decent, business-grade router (the ones that are on-topic here) is often able to handle a few million connections for NAT quite easily, so 100 or 200 even heavy users wouldn't be a problem.
Using a software router is definitely one solution - there's plenty of memory and processing power in a standard PC/server. But depending on the requirements for physical space, low latency, power consumption and cooling it might not be the best one.
