The evidence for abundant liquid water on early Mars despite the faint young Sun is a long-standing problem in planetary research. Here we present new ab initio spectroscopic and line-by-line climate calculations of the warming potential of reduced atmospheres on early Mars. We show that the strength of both CO2-H2 and CO2-CH4 collision-induced absorption (CIA) has previously been significantly underestimated. Contrary to previous expectations, methane could have acted as a powerful greenhouse gas on early Mars due to CO2-CH4 CIA in the critical 250-500 cm^-1 spectral window region. In atmospheres of 0.5 bar CO2 or more, percent levels of H2 or CH4 raise annual mean surface temperatures by tens of degrees, with temperatures reaching 273 K for pressures of 1.25-2~bar and 2-10% of H2 and CH4. Methane and hydrogen produced following aqueous alteration of Mars' crust could have combined with volcanically outgassed CO2 to form transient atmospheres of this composition 4.5-3.5 Ga. Our results also suggest that inhabited exoplanets could retain surface liquid water at significant distances from their host stars.