In this article we give explicit formulae for a lift of the relative
Frobenius morphism between elliptic curves and show how one can compute this
lift in the case of ordinary reduction in odd characteristic. Our theory can
also be used in the case of supersingular reduction. By means of the explicit
formulae that describe a Frobenius lift, we are able to generalize Mestre's
2-adic arithmetic geometric mean (AGM) sequence of elliptic curves to odd
characteristic, and prove its convergence. As an application, we give an
efficient point counting algorithm for ordinary elliptic curves which is based
on the generalized AGM sequence.