The Schur multiplier $H^2(G;{\mathbb C}^\times) \cong H^3(G;{\mathbb Z})$ of a finite group is a product of its $p$-primary parts
$$H^3(G;{\mathbb Z}) = \oplus_{ p | |G|} H^3(G;{\mathbb Z}_{(p)})$$
as is seen using the transfer. The $p$-primary part $H^3(G;{\mathbb Z}_{(p)})$ depends only of the $p$-local structure in $G$ i.e., the Sylow $p$-subgroup $S$ and information about how the subgroups of $S$ become conjugate or "fused" in $G$. (This data is also called the $p$-fusion system of $G$.)
More precisely, the Cartan-Eilenberg stable elements formula says that
$$H^3(G;{\mathbb Z}_{(p)}) = \{ x \in H^3(S;{\mathbb Z}_{(p)})^{N_G(S)/C_G(S)} |res^S_V(x) \in H^3(V;{\mathbb Z}_{(p)})^{N_G(V)/C_G(V)}, V < S\}$$
One in fact only needs to check restriction to certain V above. E.g., if S is abelian the formula can be simplified to $H^3(G;{\mathbb Z}_{(p)}) = H^3(S;{\mathbb Z}_{(p)})^{N_G(S)/C_G(S)}$ by an old theorem of Swan. (The superscript means taking invariants.) See e.g. section 10 of my paper linked HERE for some references.
Note that the fact that one only need primes p where G has non-cyclic Sylow $p$-subgroup follows from this formula, since $H^3(C_n;{\mathbb Z}_{(p)}) = 0$.
However, as Geoff Robinson remarks, the group $H^3(S;{\mathbb Z}_{(p)})$ can itself get fairly large as the $p$-rank of $S$ grows. However, $p$-fusion tends to save the day. The heuristics is:
Simple groups have, by virtue of simplicity, complicated $p$-fusion, which by the above formula tends to make $H^3(G;{\mathbb Z}_{(p)})$ small.
i.e., it becomes harder and harder to become invariant (or "stable") in the stable elements formula the more $p$-fusion there is. E.g., consider $M_{22} < M_{23}$ of index 23: $M_{22}$ has Schur multiplier of order 12 (one of the large ones!). However, the additional 2- and 3-fusion in $M_{23}$ makes its Schur multiplier trivial. Likewise $A_6$ has Schur multiplier of order 6, as Geoff alluded to, but the extra 3-fusion in $S_6$ cuts it down to order 2.
OK, as Geoff and others remarked, it is probably going to be hard to get sharp estimates without the classification of finite simple groups. But $p$-fusion may give an idea why its not so crazy to expect that they are "fairly small" compared to what one would expect from just looking at $|G|$...
Let me make my comment into an answer just get things off the ground. I claim that ${\rm PSL}(n,q)$ contains $A_5$ whenever its order is divisible by $60$.
Clearly ${\rm SL}(n,q)$ contains ${\rm SL}(m,q)$ for all $m \le n$, and hence ${\rm PSL}(n,q)$ contains some central quotient of ${\rm SL}(m,q)$ (which is something between ${\rm SL}(m,q)$ and ${\rm PSL}(m,q)$). In particular, ${\rm PSL}(n,q)$ contains a central quotient of ${\rm SL}(5,q)$ for all $n \ge 5$. Since the centre of ${\rm SL}(5,q)$ has order $1$ or $5$, and $A_5$ has no perfect $5$-fold central extension, if ${\rm PSL}(5,q)$ contains $A_5$, then so does ${\rm SL}(5,q)$. Also $|{\rm PSL}(5,q)|$ is divisible by $60$ for all $q$. So it suffices to prove the claim for $n \le 5$.
The result is well-known for $n=2$.
For $n=3$, ${\rm PSL}(3,q)$ contains ${\rm PSL}(2,q)$ as the subgroup ${\rm P}\Omega(3,q)$, and $|{\rm PSL}(3,q)|$ is divisible by $60$ if and only if $|{\rm PSL}(2,q)|$ is, so the result holds.
For $n=4$, ${\rm PSL}(4,q)$ contains the subgroup ${\rm P}\Omega^-(4,q) \cong {\rm PSL}(2,q^2)$ which has order divisible by $60$ for all $q$ and hence contains $A_5$.
For $n=5$, ${\rm PSL}(5,q)$ contains $A_5$ as the image of the natural permutation representation.
Let me carry on with the classical groups. This is not too hard.
Virtually the identical argument works for the unitary groups. In dimensions $3$ and $4$ they contain the same orthogonal groups, and the permutation representation of $A_5$ clearly preserves the identity matrix as unitary form.
For the symplectic case, the obvious containment ${\rm Sp}(m,q) \le {\rm Sp}(n,q)$ for $m \le n$, $m,n$ even projects onto ${\rm PSp}(m,q) \le {\rm PSp}(n,q)$, and ${\rm PSp}(4,q)|$ is divisible by $60$ for all $q$, so it is enough to do it for $n=4$. From the ATLAS, the $4$-dimensional irreducible representation of ${\rm SL}(2,5)$ has indicator $-$ and integer character values, so its image reduces to a subgroup ${\rm SL}(2,5) < {\rm Sp}(4,q)$ for all $q = p^e$ with $p>5$. In fact it works also for $p=5$, and the cases ${\rm PSp}(4,2) \cong S_6$ and ${\rm PSp}(4,3)$ (which contains $2^4:A_5$) can be done separately.
Finally, all of the simple orthogonal groups in dimension at least $5$ contain ${\rm P}\Omega(5,q) \cong {\rm PSp}(4,q)$, so there is nothing new to do there.
Now for some of the smaller rank exceptional groups. The Suzuki groups $^2B(q)$ have order not divisible by $3$. There are containments ${\rm PSL}(2,q) < {\rm SL}(3,q) < G_2(q) < {^3D}_4(q)$, and their orders are all either divisible by $60$ or not, so that covers them. Similarly ${\rm PSL}(2,q) < {^2G}_2(q)$.
That leaves $F_4$, $^2F_4$, $E_6$ $^2E_6$, $E_7$ and $E_8$. For $^2F_4(2^{2n+1})$, I suspect that they all contain the smallest one in the class, the Tits group $^2F_4(2)'$, which (according to the ATLAS) contains $A_5$.
This is probably not the best reference, but I think Table 2 in
http://seis.bristol.ac.uk/~tb13602/docs/large_4.pdf
is enough to deal with the remaining exceptional groups. For example $F_4(q)$ contains $D_4(q)$ = $\Omega^+(8,q)$, which contains ${\rm P}\Omega(5,q)$, which we considered above. There are lots of papers around on subgroups of the exceptional groups, but it's hard to extract exactly what we want.
Best Answer
You can only really ask for a proof that avoids a particular fact or construction, if that fact or construction is difficult enough or distinct enough from the thing that you're proving. By that principle, the comments imply that it would be enough to show that Derek Holt's subgroup $\langle a,b,c,e \rangle$ has index 2 in the candidate group $\langle a,b,c,d,e \rangle$. In fact Derek's proof is good: It is easy to show that $\langle a,b,c,e \rangle$ is isomorphic to $L_2(9) = \text{PSL}(2,\mathbb{F}_9)$, which plainly has order 360. ($L_2(9)$ is also isomorphic to $A_6$, but this fact is not needed.) Once you know that, you can also quickly construct $M_{10}$ as well, since you can show that the extra generator $d$ normalizes $L_2(9)$, and that $d^2 \in L_2(9)$.
In that Usenet posting, Derek gave these expressions: $$\begin{matrix} a &=& (2\; 3\; 4)(4\; 6\; 7)(8\; 9\; 10) \\ b &=& (2\;5\;8)(3\;6\;9)(4\;7\;10) \\ c &=& (3\;5\;4\;8)(6\;7\;10\;9) \\ e &=& (1\;2)(5\;8)(6\;7)(9\;10) \end{matrix}.$$ Recall that $\mathbb{F}_9 = (\mathbb{Z}/3)[i]$. You can define a bijection $$\alpha:\mathbb{F}_9 \cup \{\infty\} \to \{1,2,\ldots,10\}$$ by the formula $$\alpha(x+iy) = 2+x+3y \qquad \alpha(\infty) = 1,$$ using the gauche embedding $\mathbb{Z}/3 = \{0,1,2\} \subseteq \mathbb{Z}$. Then it is easy to check these expressions (using more normal arithmetic in $\mathbb{F}_9$): $$a(z) = z+1 \qquad b(z) = z+i \qquad c(z) = iz \qquad e(z) = 1/z.$$ So, that's $L_2(9)$.