Magnetic reconnection is believed to be responsible for the acceleration of energetic electrons with a power-law spectrum in the solar wind and solar flares. However, recent studies of the leading mechanism of electron acceleration in reconnection, namely, acceleration by tearing instability induced multi-islands, demonstrates that this mechanism suffers from an “injection problem” for mildly relativistic reconnection acceleration. In this paper, we investigate a new type of reconnection acceleration in which an electron Kelvin-Helmholtz instability (EKHI) is driven as the current sheet reaches electron inertial length scales during magnetic reconnection with a strong guide field. Electrons are accelerated by stochastic electric fields, induced by the EKHI generated vortices that expand rapidly, and a power-law electron energy spectrum f(W) ∝ W-α with index α ~ 3.5 is produced (W is the electron kinetic energy and f(W) is the energy distribution function.) We show that the mechanism is a 2nd-order Fermi acceleration process, and the index α = (1 + 4 a2 D/R) / 2 where a = Bg/B0 which is determined by the ratio of the spatial scale of the inductive electric field D to that of vortices R and the ratio of guide field Bg to asymptotic magnetic field B0.