Question: This is almost certainly known (and maybe written down somewhere?). Is there an example of two elliptic curves $C, E/k$ that are not isomorphic, yet there is an embedding $C\hookrightarrow E\times E$ as an abelian subvariety? 

If this is known, is there a reference that talks about such things.

Answer: 
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.
By the Poincare Complete Reducibility Theorem, the **isogeny category** of abelian varieties over an arbitrary field is semisimple.

And now, with more words: if $A\_{/k}$ is an abelian variety, then: 

(i) There are simple abelian varieties (i.e., without proper, nontrivial abelian subvarieties) $B\_1,\ldots,B\_k$ such that $A \sim B\_1 \times \ldots B\_k$, where the relation $\sim$ denotes $k$-rational **isogeny**. (An isogeny $f: A \rightarrow B$ of abelian varieties is a surjective algebraic group homomorphism with finite kernel.)  

(ii) The isogeny classes of the $B\_i$'s are uniquely determined: if $C$ is any abelian subvariety of $A$, then $C$ is $k$-rationally isogenous to a direct sum of $B\_i$'s.

Applying this result to your question, we find that the possible choices for an elliptic curve $C$ inside $E \times E$ are contained in the set of elliptic curves $k$-rationally isogenous to $E$. For instance if $k = \mathbb{C}$, this will be a countably infinite set. Note that we may well have a finite morphism $C \rightarrow E \times E$ but not an embedding. Studying abelian subvarieties in the strict sense -- i.e., not up to isogeny -- is significantly trickier.