Let $c_n$ be the number of coins on the $n^{\text{th}}$ minute. Consider the ordered pair $(x_n, y_n) = (c_n, n - c_n)$, noting that each minute either $x_n$ or $y_n$ increases by 1. The number written on the $n^{\text{th}}$ minute is
$$2c_n^2 - n^2 = 2x_n^2 - (x_n + y_n)^2 = x_n^2 - 2x_ny_n - y_n^2.$$
It thus suffices to prove the slightly more general problem:
Alice starts at an arbitrary integer lattice point $(x,y) = (x_0, y_0)$. Every minute, she walks one unit right or up (corresponding to increasing $x$ or $y$ by 1), then writes down the number $f(x,y) = x^2 - 2xy - y^2$. Show that for any positive integer $m$, there will eventually be two numbers on the board that sum to a multiple of $m$.
The function $f$ has the special property of $90^\circ$ rotational anti-symmetry, i.e., taken mod $m$:
$$f(x, y) + f(y, -x) \equiv 0$$

Claim: Among the numbers written over $4m$ minutes, there is either (a) two numbers that sum to a multiple of $m$, or (b) a number which is a multiple or half-multiple of $m$.
Proof of Claim: Suppose Bob starts at integer lattice point $(u,v) = (u_0, v_0) \equiv (y_0, -x_0) \pmod{m}$. Each minute, if Alice moves right, Bob moves down; if Alice moves up, Bob moves right.
In this manner, Alice's and Bob's coordinates are always related by $(u,v) \equiv (y,-x) \pmod{m}$. In particular, whenever Alice writes down the number $f(x,y)$, Bob writes down the number $f(u,v) \equiv -f(x,y) \pmod{m}$.

It suffices to show that Alice's and Bob's paths coincide on some lattice point $(x^*, y^*)$. If this occurs, then either
1. (a) Alice and Bob reach $(x^*, y^*)$ at different times, thus Alice has written down $f(x^*, y^*)$ and $-f(x^*, y^*)$ (mod $m$) at two different times; or
2. (b) Alice and Bob reach $(x^*, y^*)$ at the same time; thus $f(x^*, y^*) \equiv -f(x^*, y^*)$ (mod $m$), so Alice has written down a multiple or half-multiple of $m$.
WLOG among Alice's first $2m-1$ moves, she moves right at least $m$ times (the alternative is that she moves up at least $m$ times, in which case a similar argument holds by swapping the axes).
Then, within Alice's first $2m-1$ moves, she passes through some lattice point $(u_0, w_0)$, where $x_0 < u_0 \le x_0 + m$ and $u_0 \equiv y_0 \pmod m$. We then select Bob's starting point as $(u_0, v_0)$ where $w_0 < v_0 \le w_0 + m$ and $v_0 \equiv -x_0 \pmod m$.
Consequently, the path $\mathcal{L}_{\text{Bob}}$ traversed by Bob within his first $2m-1$ moves starts vertically above $(u_0, w_0)$, and at distance $\le m$ from $(u_0, w_0)$. Since Bob moves down at least $m$ times and moves right at most $m-1$ times within his first $2m-1$ moves, his path $\mathcal{L}_{\text{Bob}}$ traverses within the upper-right quadrant $\{(x, y) : x \ge u_0, y \ge w_0\}$ with respect to $(u_0, w_0)$, and leaves the quadrant from the bottom edge at a distance $\le m$ from $(u_0, w_0)$ (see Figure 1).
Thus, a further $2m$ moves by Alice starting from $(u_0, w_0)$ will take her from below $\mathcal{L}_{\text{Bob}}$ to above it, guaranteeing a lattice point intersection with $\mathcal{L}_{\text{Bob}}$.
Since two multiples of $m$ or two half-multiples of $m$ sum to a multiple of $m$, thus by the claim, Alice is guaranteed to write two numbers that sum to a multiple of $m$ within $3 \cdot 4m = 12m$ moves.

Figure 1: Sample game for $m=6$. Alice's path is lightly shaded and starts at $(x_0, y_0) = (2, 1)$ which is at the bottom. Bob's path is heavily shaded and starts at $(u_0, v_0) = (7, 10)$ at the top. Alice's path after $(u_0, w_0)$ which is at the bottom left corner of the box, is guaranteed to intersect Bob's path; the intersection is the square with 2. When Bob is at the intersection, Alice has also made 5 moves is at the square with 4. The numbers written by Alice in these 2 squares sum to a multiple of $m=6$.