$\def\U#1{\underline{#1}}\def\O#1{\overline{#1}}$The bound $a_n=O(n)$ is true, in fact, we have $a_n\le\max\{16p,16q,\frac{32}3n\}$ or so. The argument is quite elementary, but a bit tedious to write down properly, hence I will only sketch it, and rely on the reader to fill in the details.

Rather than estimating $a_n$ directly, we will try to bound the position of the most significant bit of $\max_{m\le n}a_m$. Notice that $\oplus$ cannot raise this quantity, and ${}+1$ can raise it only by one bit, when it results in a power of $2$ larger than all the previously seen numbers. In this case the ${}+1$ operation involves carries all the way from the $0$th bit to the new most significant bit. Thus, the crucial thing is to investigate carries in the sequence.

For any $k\ge1$, the operations of $\oplus$ and ${}+1$ are well defined modulo $2^k$, hence we can look at the sequence $a_n\bmod2^k$. Since the sequence is uniquely reversible mod $2^k$ by $a_{n-1}=a_n\oplus(a_{n+1}-1)$, it must be *periodic* mod $2^k$.

When computing $a_n$, there is a carry from $(k-1)$th bit to $k$th bit iff $a_n\equiv0\pmod{2^k}$; for $k>1$, this holds iff there was a carry to the $(k-1)$th bit, and the $(k-1)$th bit of $a_n$ is $0$. Let us denote the $k$th bit of $a_n$ as $a_{n,k}\in\{0,1\}$.

**Case 1:** $a_n\bmod2$ (that is, $a_{n,0}$) is $\dots1111\dots$. Then there are no carries whatsoever, hence $a_n=O(1)$ and we are done.

**Case 2:** $a_n\bmod2$ is $\dots001001001\dots$ of period $3$. Carries from $0$th to $1$st bit happen at the positions of the $0$s in the period.

This again splits to two subcases:

**Case 2a:** $a_n\bmod4$ is $\dots122320122320\dots$ of period $6$. That is, the sequence of $a_{n,1}$ is $\dots\O{\U0}\U11\U1\U10\dots$, where underlines signify carries from the $0$th bit to the $1$st bit, and overlines carries from the $1$st bit to the $2$nd bit.

**Case 2b:** $a_n\bmod4$ is $\dots120300120300\dots$ of period $6$; that is, the sequence of $a_{n,1}$ is $\dots0\U1\O{\U0}1\O{\U0}\O{\U0}\dots$.

I claim that in Case 2a, for all $k\ge2$, the sequence $a_n$ has period $3\cdot2^{k-1}$ modulo $2^k$, and there is carry to the $k$th bit at exactly one position per period.

This is proved by induction on $k$. It holds for $k=2$. When going from $k$ to $k+1$, we see that the sequence $a_{n,k}$ is a $\oplus$-linear combination of:

1. A solution of the homogeneous recurrence $b_n=b_{n-2}\oplus b_{n-1}$ modulo $2$. This is either $\dots00000\dots$, or (some shift of) $\dots011011011\dots$.

2. One particular solution of $b_n=b_{n-2}\oplus b_{n-1}\oplus c_n$, where $c_n$ is the sequence of carries to the $k$th bit. By the induction hypothesis, $c_n$ is $3\cdot2^{k-1}$-periodic, and the period has the form $100\dots0$. Thus, one solution $b_n$ is given by the $3\cdot2^k$-periodic sequence consisting of $110110110\dots110$ for $3\cdot2^{k-1}$ positions, followed by $00\dots0$ for $3\cdot2^{k-1}$ positions.

Clearly, this makes $a_{n,k}$ (and thus $a_n\bmod2^{k+1}$) $3\cdot2^k$-periodic. Carries to the $(k+1)$th bit may happen only at the two positions in this period that correspond to carries to the $k$th bit; these two positions are at distance $3\cdot2^{k-1}$ apart, and they are occupied by two opposite bits: the sequence from 1. gives them the same value, whereas the sequence from 2. gives them opposite values. Thus, exactly one of them gives rise to a carry to the $(k+1)$th bit.

In Case 2b, a similar inductive argument establishes the following claim: for any $k\ge2$, $a_n\bmod2^k$ is $3\cdot2^{k-1}$-periodic, and there are exactly $3$ carries to the $k$th bit in each period. Two of these carries have the same position modulo $3$, whereas the third is at relative position $2$ modulo $3$ with respect to them.

This implies a bound on $a_n$ as follows. For a given $n$, let $k$ be the least integer such that $n<3\cdot 2^k$ and $p,q<2^{k+1}$. Thus, $2^k\le\max\{p,q,2n/3\}$. We know from above that up to $a_n$, there are at most three carries to the $(k+1)$th bit. The first of these will attain the value $2^{k+1}$, the other two may at most get to $2^{k+3}$. Thus, the most significant bit of $a_n$ is at position at most $k+3$, and $a_n<2^{k+4}\le\max\{32n/3,16p,16q\}$.