have two arduino mega 2560s
No - silly solution, no need.
-set up a multiplex.
No even sillier solution for outputting.
Is there a way to make all of the digital pins PWM?
Software PWM library but not the best solution.
Is there something on the market similar to arduino that has can control more PWMs
No.
Use an external chip. The TLC5940 is a common one, this has 16 PWM outputs of 12 bit resoloution. You can chain sevral together to get as many LEDs as you want. I would use one for all the red, one for the blue and one for the green, which means you can have 16 RGB LEDs with just 3 chips.
The other way is to use AdaFruit's neopixels and chain as many as you like, this is by far the simplest option.