The modular curve $X_0(N)$ has good reduction at all primes $p$ not dividing $N$. At such a prime, the Eichler-Shimura relation expresses the Hecke operator $T_p$ (as an element of the ring of correspondences on the points of $X_0(N)$ in $\overline{ \mathbb{F}_p }$) in terms of the geometric Frobenius map. This is already weird enough; the definitions of the Hecke operators with which I'm familiar give no indication that such a relation should be true, and the sources I've read so far give no intuition as to why such a relation should be true. (In fact, I still don't feel very comfortable with the Hecke operators themselves; I like the definition given in Milne the best so far, but any enlightening alternate definitions are welcome if they shed light on the question.)
What's much weirder, to me anyway, is an important corollary of the Eichler-Shimura relation, which says that given a cusp eigenform $f$ of weight $2$ with respect to $\Gamma_0(N)$ it is possible to construct an elliptic curve $E_f$ whose L-function is (more or less) the Mellin transform of $f$.
There are several reasons this is weird to me, but here's a specific one. The modular form $f$ satisfies a functional equation more or less by definition. Its Mellin transform therefore satisfies a corresponding functional equation (part of which has been absorbed into the fact that $f$ is written in terms of its Fourier coefficients), again more or less by definition. The zeta function of an elliptic curve, however, satisfies a functional equation because (or so I'm told) of Poincaré duality in the étale cohomology. So:
What on Earth does Poincaré duality have to do with modular symmetry?
(Ignore the above; I seem to have mixed up the local and global functional equations again.)
One of the many things that's weird about the above is that the L-function of an elliptic curve naturally has an Euler product, but for modular forms the Euler product for the Mellin transform comes about because of certain properties of the Hecke operators (which, again, I don't really understand conceptually). What do these properties have to do with multiplying local zeta functions together?
I guess I should also clarify what I mean by "intuition":
For the first part of the question, if something in the definition of the Hecke operators suggests that they should be related to the Frobenius map if certain natural things were true, and the proof of Eichler-Shimura (which I haven't really looked at yet…) consists of verifying these natural things are true, that would be great intuition. I would appreciate an answer telling me whether or not this was the case in terms of "first principles."
For the second part of the question, intuition might more naturally come from a more sophisticated perspective. Here I would appreciate an answer about the "big picture" instead, giving some vague high-level sense of how this all fits into more general things people know about automorphic forms and so forth.
Best Answer
(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.