The minisforum I got with 32 GB of RAM is easily capable of 10M NAT entries. $500, nothing more. I’ve never went above 4 million myself, as my ports would be the limiting factor with 1 IP, but it ran without issues and not even close to capping any of the hardware.
Entries itself don’t necessarily take a lot of resources, it’s how the OS is capable of handling those amount of tables. OPNsense (and pfsense) are capable of those kind of tables without much issues.