If you are content with 9600 baud you could use SoftwareSerial on the Arduino side of the Yun to connect to a Mega.
And note that connecting to one other Arduino would be easier than connecting to two of them.
Another option might be to use an ESP8266 module to add WiFi capability to the Mega.
Why limit it to 9600?
I have been looking for some place where they say explicitly the boards compatible, but no luck.
In the Arduino page in this link: https://store.arduino.cc/product/E000024?language=enThey say: "The Mux Shield II adds the capacity for up to 48 inputs or outputs on the Arduino and Arduino Mega". I don't know if when they say "Arduino" include the Yun
Now, if you are using something like Firmata as your sketch, which is a general purpose sketch that lets the Linux side generically read/write digital I/O and analog inputs, then you have a couple choices: implement the functionality of the MuxShield library on the Linux side, or modify the sketch to include the ability. Neither of those options should be a major obstacle.
...Or add a Yun Shield to that Mega 2560. That will essentially give you a single board solution that acts like the Yun, but has the power of the Mega 2560 (more pins, more memory.)...