The problem is just that certainly all of the pairs still need to be
referenced to ground somehow before going into the multiplexer IC
Use 2 multiplexers; one for one wire in your differential pair and one for the other wire. Step and repeat for all differential pairs and, feed the multiplexed (common) output pair into a differential amplifier. This is common practice for wiring (for instance) a multitude of thermocouples that are fitted to several points on a machine to be monitored.
If your inputs are powered in remote locations or they might be grounded (unintentionally or not) then you have a more complex problem because you then have to cope with ground bounce issues that may either cause poor rejection of common mode noise or, may hurt your multiplexer chips.
Would, for example, connecting one side of each of the differential
signals to ground through a ~1 megaohm resistor be suitable?
It needs to be done in a balanced way - both wires of each pair can be grounded via a 1 MΩ resistor prior to feeding into the multiplexers. It might also be a good idea to use 1 nF capacitors in parallel to handle a little surge energy. If your bandwidth is low, then 10 nF is also good (used for multiplexing thermocouples for instance).
It also doesn't hurt to use circa 1 kΩ series resistors into each multiplexer input either (balanced still). Place them between the 1 MΩ/10 nF capacitors and the actual multiplexer pins.
And, if you need a little extra security in measurement, reserve a few multiplexed channels for local 0 volts and (say) a nominal accurate voltage just in case there is any attenuation needed to be accounted for.
You should then consider using an instrumentation amplifier (instead of a differential amplifier) now that a multiplexer is being used.