The sum does not vanish when $N$ is odd. I will elaborate on François Brunault's idea.
Assume that $N$ is odd, and let $S$ be the sum in question. Working in the ring $\mathbb{Z}[z]$, we see that $S^2\equiv T\pmod{2}$, where $$T:=\sum_{k=0}^{M-1}e^{2\pi i(2k^2+k)/N}.$$ It suffices to show that $T^{2N}=(-1)^{(N-1)/2}N^N$, because then $S^{4N}\equiv 1\pmod{2}$ is a consequence. Let us write $$w:=1+i\qquad\text{and}\qquad f(z):=e^{2\pi i(2z^2+z)/N}.$$ We shall integrate on translates of the slanted line $w\mathbb{R}$, upwards. An application of the residue theorem shows that $$S=\int_{-1/2+w\mathbb{R}}\frac{f(z+N)-f(z)}{e^{2\pi i z}-1}\,dz= \int_{-1/2+w\mathbb{R}}f(z)\,(1+e^{2\pi iz}+e^{4\pi iz}+e^{6\pi iz})\,dz.$$ In the last integral, we can shift the contour to $w\mathbb{R}$, and then after writing $z=wt$ (where $t$ increases from $-\infty$ to $\infty$), it is straightforward to evaluate the four pieces coming from $1$, $e^{2\pi iz}$, $e^{4\pi iz}$, $e^{6\pi iz}$. The final result is $$T=\exp\left(\frac{\pi i}{4}-\frac{\pi i}{4N}\right)\sqrt{N}.$$ Therefore, $T^{2N}=(-1)^{(N-1)/2}N^N$, and we are done.