Note first that the allowed operation does not change the maximum $M$ of the initial sequence. Let $a_{1}, a_{2}, \ldots, a_{n}$ be the numbers obtained at some point of the process. Consider the sum
$$S = a_{1} + 2 a_{2} + \cdots + n a_{n}$$
We claim that $S$ increases by a positive integer amount with every operation. Let the operation replace the pair $(a_{i}, a_{i+1})$ by a pair $(c, a_{i})$, where $a_{i} > a_{i+1}$ and $c = a_{i+1} + 1$ or $c = a_{i} - 1$. Then the new and the old value of $S$ differ by
$$d = \left(i c + (i+1) a_{i}\right) - \left(i a_{i} + (i+1) a_{i+1}\right) = a_{i} - a_{i+1} + i (c - a_{i+1})$$
The integer $d$ is positive since $a_{i} - a_{i+1} \geq 1$ and $c - a_{i+1} \geq 0$.

On the other hand $S \leq (1 + 2 + \cdots + n) M$ as $a_{i} \leq M$ for all $i = 1, \ldots, n$. Since $S$ increases by at least 1 at each step and never exceeds the constant $(1 + 2 + \cdots + n) M$, the process stops after a finite number of iterations.

Like in the first solution, note that the operations do not change the maximum $M$ of the initial sequence. Now consider the reverse lexicographical order for $n$-tuples of integers. We say that $(x_{1}, \ldots, x_{n}) < (y_{1}, \ldots, y_{n})$ if $x_{n} < y_{n}$, or if $x_{n} = y_{n}$ and $x_{n-1} < y_{n-1}$, or if $x_{n} = y_{n}$, $x_{n-1} = y_{n-1}$ and $x_{n-2} < y_{n-2}$, etc. Each iteration creates a sequence that is greater than the previous one with respect to this order, and no sequence occurs twice during the process. On the other hand, there are finitely many possible sequences because their terms are always positive integers not exceeding $M$. Hence the process cannot continue forever.

Let the current numbers be $a_{1}, a_{2}, \ldots, a_{n}$. Define the score $s_{i}$ of $a_{i}$ as the number of $a_{j}$'s that are less than $a_{i}$. Call the sequence $s_{1}, s_{2}, \ldots, s_{n}$ the score sequence of $a_{1}, a_{2}, \ldots, a_{n}$.

Let us say that a sequence $x_{1}, \ldots, x_{n}$ dominates a sequence $y_{1}, \ldots, y_{n}$ if the first index $i$ with $x_{i} \neq y_{i}$ is such that $x_{i} < y_{i}$. We show that after each operation the new score sequence dominates the old one. Score sequences do not repeat, and there are finitely many possibilities for them, no more than $(n-1)^{n}$. Hence the process will terminate.

Consider an operation that replaces $(x, y)$ by $(a, x)$, with $a = y + 1$ or $a = x - 1$. Suppose that $x$ was originally at position $i$. For each $j < i$ the score $s_{j}$ does not increase with the change because $y \leq a$ and $x \leq x$. If $s_{j}$ decreases for some $j < i$ then the new score sequence dominates the old one. Assume that $s_{j}$ stays the same for all $j < i$ and consider $s_{i}$. Since $x > y$ and $y \leq a \leq x$, we see that $s_{i}$ decreases by at least 1. This concludes the proof.