Where does the big change in kinetic energy come from in the headwind case?

no wind: delta KE = 1/2 m(Vdownwind^2 - Vupwind^2) = 0

headwind: delta KE = 1/2 m(Vdownwind^2 - Vupwind^2) = 1/2 m Vdownwind^2 = Big Number

Both cases are observed from the same reference frame and both cases have the same change in potential energy. If energy is conserved, all that kinetic energy had to come from somewhere.