Microbial mats from over half the history of the Earth have been fossilised with intriguing ripple patterns on them, a few millimetres wide. We show that these features can be caused by a Kelvin-Helmholz-like instability, of the flow of water over a viscoelastic fluid like the protein-rich slimy matrix of a microbial colony. By a combination of analogue experiments, and linear stability analysis, we show that the conditions for the formation of such small-scale ripples should be incredibly generic, and also develop a scaling analysis for their wavelength selection. This allows us to use the structure of Kinneyia as an indicator of the growth conditions of algal mats in the deep precambrian.