Let $a$, $b$ and $c$ be the lengths of the sides of the triangle $ABC$. Using that $AD$ is an angle bisector, that the two angles $\angle ADB$ and $\angle CDA$ are complementary (hence have equal sines) and the sine rule for the triangles $ABD$ and $ADC$ one obtains
$$\frac{|BD|}{|DC|} = \frac{c}{b} \quad \text{and similarly} \quad \frac{|AE|}{|EC|} = \frac{c}{a}.$$

The points $E$, $D$, $M$ and $N$ are all on a circle if and only if opposite angles of the quadrilateral $EDMN$ add up to $180^\circ$. This is equivalent to $\angle CMN = \angle CED$ and $\angle CNM = \angle CDE$ which is equivalent to the triangles $CMN$ and $CED$ being similar. This, however, is equivalent to
$$\frac{|CE|}{|CM|} = \frac{|CD|}{|CN|}.$$
Using $a = c \cdot |CE|/|AE|$ and $b = c \cdot |CD|/|BD|$, which was shown above, and $|AE| = |CM|$, $|BD| = |CN|$, it is now straightforward to see that $E$, $D$, $M$, $N$ are concyclic if and only if $a = b$.