Solution 1 Note that the operation in the problem does not change the maximum value $M$ of the original sequence. Let the sequence obtained after some operation be $a_1, a_2, \dots, a_n$. Consider the following sum
$$S = a_1 + 2a_2 + \dots + n a_n.$$
We claim: after each operation, $S$ always increases by some positive integer amount. Suppose some operation replaces the pair $(a_i, a_{i+1})$ with $(c, a_i)$, where $a_i > a_{i+1}$, and $c$ is either $a_{i+1} + 1$ or $a_i - 1$. Then the difference between the new value and the old value of $S$ is
$$d = (i c + (i + 1)a_i) - (i a_i + (i + 1)a_{i+1}) = a_i - a_{i+1} + i(c - a_{i+1}).$$
Since $a_i - a_{i+1} \ge 1$, and $c - a_{i+1} \ge 0$, $d$ must be a positive integer.

On the other hand, since each $a_i \le M$, we get $S \le (1+2+3+\cdots+n)M$. Since $S$ increases by at least 1 after each operation, and never exceeds the fixed value $(1+2+\cdots+n)M$, the operation must terminate after finitely many steps.

Solution 2 As in Solution 1, note that the maximum value $M$ of the sequence never changes. Now consider the reverse lexicographic order on sequences of $n$ positive integers: we write $(x_1, x_2, \dots, x_n) < (y_1, y_2, \dots, y_n)$ when $x_n < y_n$, or when $x_k = y_k$ holds for all $k = j + 1, j + 2, \dots, n$ but $x_j < y_j$. Under this order, every operation makes the sequence larger, and throughout the process the same sequence never appears twice.

On the other hand, since each term is a positive integer with a fixed maximum value, there are only finitely many possible sequences. Therefore this operation cannot proceed indefinitely.

Solution 3 Suppose the current sequence is $a_1, a_2, \dots, a_n$. Let $s_i$ denote the number of terms in this sequence that are less than $a_i$. Call the sequence $s_1, s_2, \dots, s_n$ the score sequence of the sequence $a_1, a_2, \dots, a_n$.
For two sequences $x_1, x_2, \dots, x_n$ and $y_1, y_2, \dots, y_n$, if at the index $i$ with the largest value such that $x_i \neq y_i$ we have $x_i < y_i$, we say the sequence $x_1, x_2, \dots, x_n$ beats the sequence $y_1, y_2, \dots, y_n$. We claim: after each operation, the new score sequence will beat the original score sequence. Once this property is proven, since the score sequence never repeats, and there are only finitely many possible score sequences, the operation must terminate after finitely many steps.
Consider the operation that changes $(x, y)$ into $(a, x)$, where $a = y + 1$ or $a = x - 1$. Suppose $x$ originally appeared at the $i$-th position. For every $j < i$, $s_j$ does not increase after the operation, because $y \le a$ and $x \le x$. If for some $j < i$, $s_j$ decreases, then the new score sequence beats the original score sequence. If for every $j < i$, $s_j$ remains unchanged, look at $s_i$: since $x > y$ and $y \le a \le x$, we get that $s_i$ decreases by at least 1. This completes the proof.