(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.
Harmonic analysis is the theory of representations of locally compact abelian groups. The integers, and the integers mod $n$, are such groups. For problems dealing with functions on these groups that are related to their group structure, harmonic analysis is a natural tool.
Best Answer
See
(Image from that paper, via Wikipedia)