The proof I saw was using, essentially, the Hausdorff Maximality Principle.
Hausdorff Maximality Principle (HMP). Every partially ordered chain has a $\subseteq$-maximal chain.
Clearly if $(P,\leq)$ is a partially ordered set satisfying the conditions for Zorn's lemma, and $C\subseteq P$ is a maximal chain then $C$ has an upper bound $c$ and by the maximality of $C$ we have to have $c\in C$ and that it is a maximal element.
The proof seems to go through other means to prove HMP, and it uses the Bourbaki-Witt theorem.
The Bourbaki-Witt theorem does not rely on the axiom of choice at all. It is provable in ZF, as remarked by Brian here. The reason it is provable in ZF is that it assumes the existence of a least upper bound of every chain, and therefore allows a canonical choice for $a_1$ when moving from $D_0$ to $D_1$ (and so on).
The axiom of choice comes in, full-blown power, in the proof of Corollary 2.4:
Suppose that $A$ does not have a maximal element. Then for each $x\in A$ there is an element $y_x\in A$ such that $x<y_x$. Let $f\colon A\to A$ be the map such that $f(x)=y_x$ for all $x\in A$.
Here we actually say that $f$ is a choice function. In the proof of the Bourbaki-Witt theorem we needed to know what is the next step in "growing up", but we assumed that $f$ was given to us. From that it was just a matter of finishing the proof.
But in this corollary we need to actually define $f$. And this requires the axiom of choice.
I should add that there are books full of equivalents to the axiom of choice, and there are a lot of them which are very not-set theoretical axioms, or very unrelated to well-ordering (e.g. "Every non-empty set can be made into a group"). Since they are all equivalent to the axiom of choice, all of them are equivalent to Zorn's lemma.
Here's one idea. Use the following consequence of Nakayama:
If $M$ is a finitely generated $R$-module and $f\colon M\to M$ is a surjective module homomorphism, then $f$ is an isomorphism.
Proof: View $M$ as an $R[x]$-module, where the action of $x$ on $M$ is given by $f$. By assumption $xM = M$. The proof of Nakayama's lemma then gives that there is some element $P(x)\in R[x]$ such that $(1 - P(x)x)M = 0$. Then for any $m\in M$, $$0 = (1 - P(x)x)m = m - P(f)(f(m))\implies m = P(f)(f(m)).$$ This shows that $P(f)$ is an inverse of $f$.
To use this to prove FGFM, do the following. Suppose $n\geq m$, and that $R^n\cong R^m$. First, fix a basis $e_1,\ldots, e_n$ of $R^n$, and identify $R^m$ with the submodule of $R^n$ generated by $e_1,\ldots, e_m$, so $R^m\subseteq R^n$. Let $\pi\colon R^n\to R^m$ be the projection map. Since by assumption $R^n\cong R^m$, there is some isomorphism $f\colon R^m\to R^n$. But then $\pi\circ f\colon R^m\to R^m$ is surjective, and hence by the result above, is also an isomorphism. However, since $f$ is surjective, the only way that $\pi\circ f$ can be an isomorphism is if $\pi$ is injective. This of course only happens when $n = m$.
Best Answer
Andreas Blass proved in
Blass, Andreas, Injectivity, projectivity, and the axiom of choice, Trans. Am. Math. Soc. 255, 31-59 (1979). ZBL0426.03053.
that the statement "every free abelian group is projective" is equivalent to the axiom of choice.