That simplicity you speak of means nothing inherently in chemistry, just because it's a simple molecule doesn't mean it will be anywhere. In fact, the sun's radiation degrades methane in the atmosphere, plus the Martian atmosphere is very thin and thinning over time. How then to account for new sources of methane observed by recent observations?

Microbes is one exciting option. Methanogenesis is the process of the production of methane in microbes. It occurs in anaerobic respiration (i.e. the microbes wouldn't need oxygen to make methane - check on Mars). It's the final step in the consumption of old biomass. So, presumably, one could've had microbes feeding on old organic material spewing methane. It would explain why there are spikes in the methane levels, as the sun's radiation would have degraded any old methane over time.

The other option is some sort of volcano or fissure in the planet's surface, which would allow a geochemical source of methane, I don't know much about that process though.