(1) Short answer to first question: $T_p$ is about $p$-isogenies, and in char. $p$ there is a canonical $p$-isogeny, namely Frobenius.
Details:
The Hecke correspondence $T_p$ has the following definition, in modular terms:
Let $(E,C)$ be a point of $X_0(N)$, i.e. a modular curve together with a cyclic subgroup
of order $N$. Now $T_p$ (for $p$ not dividing $N$) is a correspondence (multi-valued function) which maps
$(E,C)$ to $\sum_D (E/D, (C+D)/D)$, where $D$ runs over all subgroups of $E$ of degree $p$.
(There are $p+1$ of these.)
Here is another way to write this, which will work better in char. $p$:
map $(E,C)$ to $\sum_{\phi:E \rightarrow E'}(E',\phi(C)),$
where the sum is over all degree $p$ isogenies $\phi:E\rightarrow E'.$ Giving a degree
$p$ isogeny in char. 0 is the same as choosing a subgroup of order $D$ of $E$ (its kernel),
but in char. $p$ the kernel of an isogeny can be a subgroup scheme which is non-reduced,
and so has no points, and hence can't be described simply in terms of subgroups of points.
Thus this latter description is the better one to use to compute the reduction of the
correspondence $T_p$ mod $p$.
Now if $E$ is an elliptic curve in char. $p$, any $p$-isogeny $E \to E'$ is either
Frobenius $Fr$, or the dual isogeny to Frobenius (often called Vershiebung).
Now Frobenius takes an elliptic curve $E$ with $j$-invariant $j$ to the elliptic curve
$E^{(p)}$ with $j$-invariant
$j^p$. So the correspondence on $X_0(N)$ in char. $p$ which maps $(E,C)$ to $(E^{(p)},
Fr(C))$ is itself the Frobenius correspondence on $X_0(N)$. And the correspondence
which maps $(E,C)$ to its image under the dual to Frobenius is the transpose
to Frobenius (domain and codomain are switched). Since there are no other $p$-isogenies in char. $p$
we see that $T_p$ mod $p = Fr + Fr'$ as correspondences on $X_0(N)$ in char. $p$;
this is the Eichler--Shimura relation.
(2) Note that only weight 2 eigenforms with rational Hecke eigenvalues give elliptic curves;
more general eigenforms give abelian varieties.
An easy computation shows that if $f$ is a Hecke eigenform, than the $L$-funcion
$L(f,s)$, obtained by Mellin transform, has a degree 2 Euler product. A more conceptual answer would probably involve describing how automorphic representations
factor as a tensor product of local factors, but that it a very different topic from Eichler--Shimura, and I won't say more here.
Dear Evgeny,
The paper Congruence relations on some Shimura varieties of Wedhorn (and some follow-up papers) proves what is (I think) the state of the art on Eichler--Shimura relations on higher dimensional Shimura varieties. Namely, he establishes the congruence relation for a wide class of PEL Shimura varieties. Just as you surmise, the density of the ordinary locus plays an important role in his argument.
Regards,
Matt
Best Answer
Surprisingly, the case of modular curves is misleading! General theory of correspondences, plus the theory of the mod $p$ reduction of curves like $X_0(Np)$ ($p$ doesn't divide $N$) give a relationship between the Hecke operator $T_p$ and the Frobenius endomorphism $Frob_p$ acting on, say, the Jacobian of a modular curve. But now there's a coincidence: from this data we can figure out a degree two polynomial satisfied by $Frob_p$ on the chunk of the Tate module of the Jacobian which corresponds to a given weight 2 eigenform, and we know for other reasons that this chunk is 2-dimensional, and it's not hard to tease out from this a proof that the degree two poly we know must be the char poly of Frobenius. I would recommend Brian Conrad's appendix to the Ribet-Stein paper for a modern treatment of this story.
But pretty much the moment one leaves the relative safety of curves, this trick doesn't work, because the arithmetic geometry gives you a polynomial which kills Frobenius, but you don't have enough information to check that this poly is the char poly. So you have to do something vastly more complicated! This vastly more complicated thing was figured out by Langlands in the case of modular curves (the details are mostly buried in his Antwerp paper). Another place to look for the modular curve case is Clozel's Bourbaki article from about 1993, although he skips many of the details when it comes to cusps and supersingular points.
OK so Langlands' proof looks like this. We need to check that the $L$-function of a modular curve is a product of $L$-functions coming from automorphic forms. The $L$-function of a modular curve is a product of local terms, and the local term at $p$ can be computed if one knows the number of $k$-points on the curve for $k$ running through all finite fields of char $p$. The goal is to relate these numbers to numbers coming from the theory of automorphic forms---basically numbers related to the Hecke operators at $p$. Langlands observes however that he can count the number of $k$-points on a modular curve: there are cusps, which aren't too hard, and then there are supersingular points, which come out as some explicit number, and then there are ordinary points, which he counts isogeny class by isogeny class. Langlands can compute isogeny classes using Honda-Tate theory and then he writes a formula for the size of each isogeny class, via some manipulations with lattices, as an integral over some adele group (the point is that you use the Tate module of the curve at $\ell$ to understand $\ell$-power isogenies, and then rewrite such things as integrals over $\ell$-adic groups, and then take the product over all $\ell$).
The resulting equation is a horrific mess, which can basically be almost completely written in terms of twisted orbital integrals on $GL(2)$ and various subgroups. The reason the orbital integrals are twisted is that the arguments for isogenies at $p$ use the Dieudonne module of the curve, so one has to do semilinear algebra here to count subgroups of $p$-power order.
Next Langlands uses the Fundamental Lemma for $GL(2)$, which he can prove with his bare hands, to turn his twisted orbital integrals into orbital integrals.
Finally, Langlands looks at the resulting mess and says "oh look, this is just precisely the geometric side of the trace formula! So it equals the spectral side.". And then he looks to see what he has proved, and he's proved that the size of $X_0(N)(k)$ equals the trace of some Hecke operator (depending on $k$) and he figures out how this trace relates to $T_p$ and then he's proved Eichler-Shimura.
I know of no complete reference for the above argument. In particular, checking that the "nasty" terms in the trace formula coming from the fact that we're in the non-compact case, match up precisely with the number of cusps, is something so deeply embedded in Langlands Antwerp that I have never really managed to get it out.
This method is much more complicated than Eichler-Shimura, but it generalises much better. By Corvallis they basically had got it working for forms of $GL(2)$ over a totally real field, where already the arithmetic geometry methods were struggling. See the articles of Kottwitz, Milne, Casselman etc.
Later on Kottwitz pushed the method through for a wide class of PEL Shimura varieties, but I'm not sure he did it for all of them. This is what prompted Clozel's Sem Bourbaki talk in 1993 or so---I mentioned this earlier. I think Milne has written a lot about this area recently though, in particular I believe he's trying to debunk the myth that the result is proved for all PEL Shimura varieties. See in particular Milne's paper "Points on Shimura varieties over finite fields: the conjecture of Langlands and Rapoport" (2008) available here for example.