Of course that $E$ does not have to be well-founded. The decreasing sequence cannot be a member of $M$, though. In such case the $M$ does not know that $E$ is not well-founded.
For example, suppose that $\langle N,\in\rangle$ is a model of ZFC and $U$ is a free ultrafilter over $\omega$. Let $\langle M,E\rangle$ be the ultraproduct of $\langle N,\in\rangle$ by the ultrafilter $U$. By Los theorem $\langle M,E\rangle$ has to be a model of ZFC.
Namely $M=N^\omega/U$, and if $f\colon\omega\to N$ then $[f]_U = \{g\colon\omega\to N\mid f\equiv_U g\}$, where $f\equiv_U g\iff\{n\in\omega\mid f(n)=g(n)\}\in U$. And $E=\{\langle [f],[g]\rangle\mid f\in_U g\}$, where $f\in_U g\iff\{n\in\omega\mid f(n)\in g(n)\}\in U$.
Now I claim that $E$ is not well-founded. Let $f_n(k)=\max\{0,k-n\}$ (namely, $n$ zeros, and then start writing the natural numbers). I claim that $f_{n+1}\mathrel E f_n$ for all $n$, but that is obvious because on a final segment $f_{n+1}(k)=k-n-1\in k-n=f_n(k)$, therefore $\langle [f_n]\mid n\in\omega\rangle$ is a sequence showing that $E$ is not well-founded. This sequence, however, is not an element of $M$ (nor corresponds to one).