12. 2004

From $|a-b| \leqslant \max \{a, b\}$ (where $a, b$ are non-negative numbers), it follows that $||a-b|-c| \leqslant \max \{|a-b|, c\} \leqslant \max \{a, b, c\}$, which leads to $M \leqslant 2004$.

On the other hand, $||2003-2002|-2001|-2000|=0$, $|||1999-1998|-1997|-1996|=0$, ..., $||7-6|-5|-4|=0$, $||3-2|-1|=0$. Let $x_{2004}=2004$, then $M$ can be equal to 2004.
12. $\left(x_{1}, x_{2}, \cdots, x_{2004}\right)$ is a permutation of $1,2,3, \cdots \cdots, 2004$, let $M=\|\cdots\|$ $\left|x_{1}-x_{2}\right|-x_{3}\left|-x_{4}\right|-\cdots\left|-x_{2004}\right|$, then the maximum value of $M$ is $\qquad$