Giving a morphism $C \to E\times E$ is the same as giving a pair of morphisms $p,q: C \to E$, by the definition of the product. Translating $p$ and $q$ appropriately by some points of $E$, it is no loss of generality to assume that $p$ and $q$ both take the origin of $C$ to the origin of $E$, and hence are not only morphisms of curves, but homomorphisms of elliptic curves.
The map $C \to E \times E$ will be injective if and only if $ker(p) \cap ker(q) = 0$.
Now if $q^{\vee}$ denotes the dual of $q$, then $q^{\vee}\circ p$ is an endomorphism of $C$. If $C$ (equivalently, $E$) is not CM, then this will be multiplication by some integer $n$, in which case we find (composing with $q$) that $\deg(q) p = n q$, and a short argument shows that in fact there is an morphism $r: C \to E$ such that $p = m r$ and $q = n r$ for some integers $m$ and $n$. If $ker(p)\, $ and $ker(q)\, $ have trivial intersection, it follows that $r$ must be an isomorphism, so that $C \cong E$.
On the other hand, if $E$ has CM, then the situation you ask about can occur. The easiest case is to assume that $E$ and $C$ both have CM by the full ring of integers $\mathcal O$ in some imag. quad. field $K$, but are not isomorphic (which is possible iff $K$ has class number bigger than one). Then $Hom(C,E)$ is an $\mathcal O$-module, invertible (i.e. locally free of rank one) but not free. Such a module can always be generated by two elements. If we take $p$ and $q$ to be a pair of generators, then they will embed $C$ into $E\times E$.
If $E$ has CM by a field of class number one, then the same kind of construction should be possible, I think, by choosing $C$ to have CM by some proper order of $K$ with non-trivial class number.