So make them larger -- as large as you can get with the tips not quite going supersonic. (The speed of sound on Mars (probably around 540 mph at ground level) is a bit lower than it it is on Earth thanks to the low pressure, low temperatures and mostly CO2 atmosphere, so that's an even bigger problem.)
More blades as well -- not just 2, but 3, 4, 5, 6, whatever. There's diminishing returns past two (well, one!) but it can help when you don't mind using a lot more power for a little more thrust.
Go for fatter blades and higher pitches as well -- more diminishing returns, but it could still help.
If you're thinking of a multicopter as I imagine they are, go with more than four propellers. Putting propellers on top of other propellers could help as well, but again ... diminishing returns.
It's not trivial, but it should be doable.
Or maybe they could even let the tips go supersonic ... it might be less of a problem with such a thin atmosphere than it would be here. I'm not so sure about this.
so simply applying a scaling law like that isn't very accurate.
It's a good "back of the napkin" first order approximation. I'd expect NASA to take everything into consideration, model it exactly, and then actually build it and fly it in a chamber that approximates the atmosphere of Mars.
It doesn't need high performance or duration -- just enough to go almost straight up and pan around and take pictures and then land back and charge up again.