One possibility is to rewrite as $$M^2=(2N)^2+(N+1)^2. $$ So you are looking at the Pythagorean triples of the form $(N+1,2N,M) $.
Edit: Along the lines of Erick's complaint, I want to make this into a full answer, so let's talk about Pythagorean triples and how this turns into an acceptably fast algorithm.
A primitive Pythagorean triple is a triple $(r^2-s^2, 2rs, r^2+s^2)$ where $r$ and $s$ are coprime positive integers, not both odd, and $r>s$. It turns out that every Pythagorean triple -- a triple of positive integers $(a,b,c)$ where $a^2+b^2=c^2$ -- is a positive integer multiple of a primitive Pythagorean triple.
If $(N+1, 2N, M)$ is a Pythagorean triple, then there are positive integers $r$, $s$, and $k$ as above where $N+1=k(r^2-s^2)$ and $2N=2krs$. Since $2N=2((N+1)-1)$, this means $2krs=2(k(r^2-s^2)-1)$, so $krs=kr^2-ks^2-1$, so $k(rs-r^2+s^2)=-1$. Since $k$ is a positive integer, this means $k=1$, so that's one degree removed.
So we're looking at positive integers $r$ and $s$ where $rs-r^2+s^2=-1$, or rearranged, $s^2+rs-r^2+1=0$. So it must be that $s=\frac{1}{2}\left(-r+\sqrt{r^2+4(r^2-1)}\right)=\frac{1}{2}\left(-r+\sqrt{5r^2-4}\right)$.
Note that it's $+$, not $\pm$, in the above, since $s$ needs to be positive. Thus, given $r$, we can find $s$.
So the algorithm is now this. For each positive integer $r$, find $s$ in the above. If it's a positive integer, then $N=rs$, and you've found a solution $N$. Every $N$ is of this form, so this enumerates all of them, in order.
Additionally, if some number $N$ is a solution, this algorithm will find it in $O(\sqrt{N})$ time.
It can be sped up by enumerating solutions to the Pell-like equation $5r^2-4=t^2$ (that is, finding $r$ which make $s$ rational), which can be done very quickly through a recurrence (I believe) but I don't actually know how to do it. If you can do that, about half of those $r$ should make $s$ an integer, as opposed to merely rational, and you've got a really fast algorithm.