(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.
Caveat: in order to give you an overview, I've been vague/sloppy in several places.
Well the basic link to representation theory is that modular forms (and automorphic forms) can be viewed as functions in representation spaces of reductive groups. What I mean is the following: take for example a modular form, i.e. a function $f$ on the upper-half plane satisfying certain conditions. Since the upper-half plane is a quotient of $G=\mathrm{GL}(2,\mathbf{R})$, you can pull $f$ back to a function on $G$ (technically you massage it a bit, but this is the main idea) which will be invariant under a discrete subgroup $\Gamma$. Functions that look like this are called automorphic forms on $G$. The space all automorphic forms on $G$ is a representation of $G$ (via the right regular represenation, i.e. $(gf)(x)=f(xg)$). Basically, any irreducible subrepresentation of the space of automorphic forms is what is called an automorphic representation of $G$. So, modular forms can be viewed as certain vectors in certain (generally infinite-dimensional) representations of $G$. In this context, one can define the Hecke algebra of $G$ as the complex-valued $C^\infty$ functions on $G$ with compact support viewed as a ring under convolution. This is a substitute for the group ring that occurs in the representation theory of finite groups, i.e. the (possibly infinite-dimensional) group representations of $G$ should correspond to the (possibly infinite-dimensional) algebra representations of its Hecke algebra. This type of stuff is the basic connection of modular forms to representation theory and it goes back at least to Gelfand–Graev–Piatestkii-Shapiro's Representation theory and automorphic functions. You can replace $G$ with a general reductive group.
To get to more advanced stuff, you need to start viewing modular forms not just as functions on $\mathrm{GL}(2,\mathbf{R})$ but rather on $\mathrm{GL}(2,\mathbf{A})$, where $\mathbf{A}$ are the adeles of $\mathbf{Q}$. This is a "restricted direct product" of $\mathrm{GL}(2,\mathbf{R})$ and $\mathrm{GL}(2,\mathbf{Q}_p)$ for all primes $p$. Again you can define a Hecke algebra. It will break up into a "restricted tensor product" of the local Hecke algebras as $H=\otimes_v^\prime H_v$ where $v$ runs over all primes $p$ and $\infty$ ($\infty$ is the infinite prime and corresponds to $\mathbf{R}$). For a prime $p$, $H_p$ is the space of locally constant compact support complex-valued functions on the double-coset space $K\backslash\mathrm{GL}(2,\mathbf{Q}_p)/K$ where $K$ is the maximal compact subgroup $\mathrm{GL}(2,\mathbf{Z}_p)$. If you take something like the characteristic function of the double coset $KA_pK$ where $A_p$ is the matrix with $p$ and $1$ down the diagonal, and look at how to acts on a modular form you'll see that this is the Hecke operator $T_p$.
Then there's the connection with number theory. This is mostly encompassed under the phrase "Langlands program" and is a significantly more complicated beast than the above stuff. At least part of this started with Langlands classification of the admissible representation of real reductive groups. He noticed that he could phrase the parametrization of the admissible representations say of $\mathrm{GL}(n,\mathbf{R})$ in a way that made sense for $\mathrm{GL}(n,\mathbf{Q}_p)$. This sets up a (conjectural, though known now for $\mathrm{GL}(n)$) correspondence between admissible representations of $\mathrm{GL}(n,\mathbf{Q}_p)$ and certain $n$-dimensional representations of a group that's related to the absolute Galois group of $\mathbf{Q}_p$ (the Weil–Deligne group). This is called the Local Langlands Correspondence. The Global Langlands Correspondence is that a similar kind of relation holds between automorphic representations of $\mathrm{GL}(n,\mathbf{A})$ and $n$-dimensional representations of some group related to Galois group (the conjectural Langlands group). These correspondences should be nice in that things that happen on one side should correspond to things happening on the other. This fits into another part of the Langlands program which is the functoriality conjectures (really the correspondences are special cases). Basically, if you have two reductive groups $G$ and $H$ and a certain type of map from one to the other, then you should be able to transfer automorphic representations from one to the other. From this view point, the algebraic geometry side of the picture enters simply as the source for proving instances of the Langlands conjectures. Pretty much the only way to take an automorphic representation and prove that it has an associated Galois representation is to construct a geometric object whose cohomology has both an action of the Hecke algebra and the Galois group and decompose it into pieces and pick out the one you want.
As for suggestions on what to read, I found Gelbart's book Automorphic forms on adele groups pretty readable. This will get you through some of what I've written in the first two paragraphs for the group $\mathrm{GL}(2)$. The most comprehensive reference is the Corvallis proceedings available freely at ams.org. To get into the Langlands program there's the book an introduction to the Langlands program (google books) you could look at. It's really a vast subject and I didn't learn from any one or few sources. But hopefully what I've written has helped you out a bit. I think I need to go to bed now. G'night.
Best Answer
My interpretation of the quote is different. (Granted, whether Eichler really said such a thing is a different question). It should refer to solving the algebraic equations, to the legacy of Abel and Galois and to Kronecker's Jugendtraum! To the book of Taniyama and Shimura, whereby certain abelian equations are solved by adjoining the moduli of a relevant abelian variety. In this sense, from the point of view of exact solutions to algebraic equations, the modular functions such as $j$ are indeed a natural, inevitable complement to the basic arithmetic operations $+, \times, \sqrt[n]{\cdot}$. This falls into the rubric of explicit class field theory. For a connection to modular forms such as $\Delta(\tau)$, see Ribet's converse to Herbrandt's theorem; a great introduction to this circle of ideas is Mazur's article, "How can we construct abelian Galois extensions of basic number fields?" (Bull. AMS, vol. 48, no. 2, pp. 155-209).