What fragment of ZFC do we need to prove Zorn's lemma?

Actually, one does not need to use any ordinals to prove Zorn's lemma in RZC!

Theorem: Every non-empty partial order $(S,<)$ in which every non-empty chain has an upper bound has a maximal element.

Proof: We shall work under the assumption that the claim is false. First let $F$ be a choice-function that maps each chain $C$ in $(S,<)$ to a strict upper bound for $C$ in $S$. (This is the only use of AC in this proof, and also shows that it suffices for $S$ to be well-orderable in absence of AC.) We say that $T$ is a tower iff $T$ is a well-ordered chain in $(S,<)$ and $∀x{∈}T\ ( \ x = F(T_{<x}) \ )$. Note that any two towers $T,U$ agree, meaning that one is a subchain of the other, since otherwise $T{∖}U$ and $U{∖}T$ are both non-empty and disjoint and so letting $m = \min_<(T{∖}U)$ and $n = \min_<(U{∖}T)$ we would obtain $m = F(T_{<m}) = F(U_{<n}) = n$ and hence a contradiction. Now let $V$ be the union of all the towers, and observe by the above note that it is a tower too, but that $V∪{F(V)}$ is a taller tower, contradicting the definition of $V$.

The argument proposed by Zhen Lin works once one knows that $Y$ (as defined there) is well-ordered by the "obvious" relation $\prec$, namely that one equivalence class is smaller than another if some (equivalently every) element of the first class embeds as a proper initial segment in some (equivalently every) element of the second class. Zhen Lin leaves this issue unsettled when $\mathbb N$ doesn't exist, but even when $\mathbb N$ does exist, the proposed argument doesn't work. The reason is that it uses the equivalence between "well-ordered" and "has no decreasing $\omega$-sequence"; this equivalence is not provable in the absence of the axiom of choice (more precisely, it needs the principle of dependent choice (DC), which is one of the weak forms of AC). So here's a proof, without $\mathbb N$ and without DC, that $Y$ is well-ordered.

Let $Z$ be a nonempty subset of $Y$; we need to show that $Z$ has a smallest element. Consider any element $[R]$ of $Z$. By the notation $[R]$ I mean the isomorphism class of a well-ordering $R\in\mathcal F$ (still using the notation of Zhen Lin's answer). If $[R]$ is the smallest element of $Z$, we're done, so assume it is not. This means that $Z$ has other elements $[S]$ whose elements $S$ are embeddable as initial segments of $R$. Each such initial segment is, since $R$ is a well-order, of the form $\{x:xRa\}$ for some $a$ in the field of $R$. Let $Q$ be the set of those elements $a$ that arise in this way, i.e., the set of those $a$ in the field of $R$ such that the initial segment consisting of the $R$-predecessors of $a$ (ordered by the restriction of $R$) is in one of the isomorphism classes in $Z$. Because $R$ is well-ordered, $Q$ has a smallest element $b$. It is then easy to check that the isomorphism class of $\{x:xRb\}$ (again ordered by the restriction of $R$) is the smallest element of $Z$.