We present a mathematical theory to study the origin of large-scale spiral troughs on the Mars residual polar caps, starting with the hypothesis that atmospheric circulation governs the planform of the troughs via an instability that operates in the flow direction of surface winds. This concept can explain why the troughs spiral at each pole in an opposite sense to that expected for Coriolis-deflected winds. The instability arises from interactions on water ice, assumed to contain dust, and depends on how the exchange of atmospheric dust and moisture (H2O) with the polar cap surface controls its albedo and mass and energy balance. Our model predicts spatial patterns to form when moisture is carried by wind over the surface, owing to unstable coupling between the albedo and the H2O-vapor pressure. The resulting albedo pattern causes an alternating "accumulation-ablation" mass balance, so that an undulating topography develops which resembles the (dark) troughs and their adjacent (bright) smooth terrains on the polar caps. Because the albedo patterning process is fast, whereas topographic evolution is slow, we suggest that an ancient imprint in the surface albedo preconditions today's trough morphology.