Here's a nice proof that uses group actions.
Let $x_1,\ldots,x_n$ be $n$ unknowns, and consider
$$\Delta= \prod_{1\leq i\lt j\leq n} (x_j-x_i).$$
For example, for $n=4$, we would have
$$\Delta = (x_2-x_1)(x_3-x_1)(x_4-x_1)(x_3-x_2)(x_4-x_2)(x_4-x_3).$$
Given a permutation $\sigma\in S_n$, define a function $f_{\sigma}\colon \{\Delta,-\Delta\} \to \{\Delta,-\Delta\}$ by letting
$$f_{\sigma}(\Delta) = \prod_{1\leq i\lt j\leq n} (x_{\sigma(j)}-x_{\sigma(i)}),$$
and $f_{\sigma}(-\Delta)=-f_{\sigma}\Delta$.
Note that since $\sigma$ is a permutation, $f_{\sigma}(\Delta)=\Delta$ or $f_{\sigma}(\Delta) = -\Delta$. Also, if $\sigma,\rho$ are two permutations, then $f_{\sigma}\circ f_{\rho} = f_{\sigma\rho}$, as is easy to verify.
Now, let's consider what a transposition $\tau=(a,b)$ does to $\Delta$. Without loss of generality, say $a\lt b$.
The factors $(x_j-x_i)$ with neither $i$ nor $j$ equal to $a$ nor $b$ are unchanged.
For the pairs with exactly one index in $\{a,b\}$, we have two classes: those in which the other index is between $a$ and $b$, and those where the other index is not between $a$ and $b$.
If the other index is between $a$ and $b$, then $x_j-x_a$ is sent to $-(x_b-x_j)$ and $x_b-x_j$ is sent to $-(x_j-x_a)$; the two sign changes cancel each other out.
If the other index is larger than $b$, then $x_j-x_a$ and $x_j-x_b$ are swapped, with no sign changes.
If the other index is smaller than $a$, then $x_a-x_i$ and $x_b-x_i$ are swapped, with no sign changes.
Finally, the factor $x_b-x_a$ is sent to $-(x_b-x_a)$.
In summary, if $\tau$ is a transposition, then $f_{\tau}(\Delta)=-\Delta$, $f_{\tau}(-\Delta)=\Delta$.
Now take an arbitrary permutation $\sigma$, and express it as a product of transpositions in two different ways:
$$\sigma = \tau_1\cdots \tau_r = \rho_1\cdots\rho_s.$$
Then
$$f_{\sigma}(\Delta) = f_{\tau_1\cdots\tau_r}(\Delta) = f_{\tau_1}\circ\cdots\circ f_{\tau_r}(\Delta) = (-1)^r\Delta$$
and
$$f_{\sigma}(\Delta) = f_{\rho_1\cdots\rho_s}(\Delta) = f_{\rho_1}\circ\cdots\circ f_{\rho_s}(\Delta) = (-1)^s\Delta.$$
Therefore, $(-1)^r\Delta = (-1)^s\Delta$, so $r$ and $s$ have the same parity: both odd, or both even.
The order of a permutation is the least common multiple of its cycle lengths. If the order is $4$, all cycle lengths must be $1$, $2$ or $4$, and at least one must be $4$. The cycle lengths must add up to $6$. That leaves the two options $4,2$ and $4,1,1$. The first is even and the second odd, so the only odd permutations of order $4$ in $S_6$ are the $4$-cycles. These can be counted by choosing the two fixed points in $\binom62$ ways and choosing one of $3!$ cyclically inequivalent orders in the $4$-cycle, for a total of $\binom62\cdot3!=90$.
Best Answer
Let $\text{Odd}_n$ denote the set of odd permutations in $S_n$. Fix an element $\alpha \in \text{Odd}_n$, and define a function $f\colon A_n \to \text{Odd}_n$ by $$ f(\sigma) \;=\; \alpha\sigma. $$ I claim that $f$ is a bijection.
To prove that $f$ is one-to-one, suppose that $f(\sigma) = f(\sigma')$ for some $\sigma,\sigma' \in A_n$. Then $\alpha\sigma = \alpha\sigma'$, and therefore $\sigma=\sigma'$.
To prove that $f$ is onto, let $\beta \in \text{Odd}_n$. Then $\alpha^{-1}\beta$ is an even permutation and $f(\alpha^{-1}\beta) = \beta$, which proves that $f$ is onto.
We conclude that $|A_n| = |\text{Odd}_n|$, and therefore $|A_n| = |S_n|/2$.