Everything that follows is over $\mathbb{C}$. Consider an elliptic curve $E$. Then, there is an isomorphism $$ Pic(E\times E)\cong Pic E\times Pic E\times Hom(JE,JE), $$ where $JE$ is the Jacobian of $E$, i.e., $Pic^0E\cong E$. Therefore, $$ Pic(E\times E)\cong (E\times\mathbb{Z})\times (E\times\mathbb{Z})\times \mathbb{Z}/n\mathbb{Z} $$ for some $n$ depending on the $j$-invariant of the curve (this is a result from Hartshorne).
This means that the Picard group of the product is generated by multiples of elements of the form $E\times p$, $p\times E$ and the diagonal $\Delta$ (which I'm assuming corresponds to the generator of the cyclic group in the decomposition).
On the other hand, the first Chern class defines a surjection $c_1:Pic(E\times E)\to H^{1,1}(E\times E)$ and by Kunneth's formula $\dim_\mathbb{C} H^{1,1}(E\times E)=4$.
This seems contradictory to me since when passing to cohomology all the classes $E\times p$ and $p\times E$ become equivalent regardless of the point $p$ we choose, yielding only 3 generators. So my question is, where did I lose the fourth generator?
The first Chern class is not a surjection onto $H^{1,1}$.
You might have in mind the Lefschetz theorem on (1,1)-classes, that says that $c_1$ is a surjection onto $H^{1,1} \cap H^2(X,\mathbf Z)$.
But the point is that the lattice $H^2(X,\mathbf Z)$ may not be "properly aligned" with the complex subspace $H^{1,1}$.
So for example for abelian surfaces, the rank of this group can be anywhere between 1 (as it is for a very general abelian surface) and 4.
(A minor point: your description of the endomorphism group $\operatorname{Hom}(JE,JE)$ is also not correct. This always has rank at least 1, because for any $n$ there is the multiplication-by-$n$ isogeny $E \rightarrow E$. Correspondingly, the diagonal $\Delta$ gives a non-torsion class in $\operatorname{Pic}(E)$, which indeed must be the case since $\Delta$ has nonzero intersection numbers with other classes.)