Understanding compression/encoding in linear time
I have checked the code, reread the paper and it seems that algorithm is not performing in $\mathcal O(n)$ in the way you have described.
The recursive calls of finding pairs works in $\mathcal O(n \log n)$ divided by constant if you wish to pack it to the end. In fact the structure underneath keeps pointers to the first occurence of pair, splits the queue of pairs by occurences to make it efficient, but still loglinear. On the other hand by analysing the code written by Ph.D. student of the author I have discovered several tricks - the length of pairs (the original name) is given as parameter (default is 2) and the recurrence is limited by parameter, which can discard further calls (default is about 5 levels), with ability to make only one pass or push to the end. The default code runs in $\mathcal O(n)$, but will not yield optimal compression. There is also switch to prefer memory, time or be neutral.

The paper and the code shows usage of hash-table, which runs only in expected constant time, but the function given works very well with characters. Also the code limits the input length by constant hardcoded.

Changing hashtable to suffix tree and rewritting the part of recurrence into bookkeepping partial pairs might yield better results - I am not sure if this is possible to make it $\mathcal O(n)$, this would be probably a different question.

There is also trick used to keep empty space from traversing - the start of empty block points to the first non-empty character, but this only speeds up traversing, still with loglinear time. The part responsible for this behaviour is replacing pairs by the new character every iteration - keeping only rewrite rules and operating on them would be faster, but still the access to check if new pairs were introduced would require to check rewrite rules against the new ones - in the case we build full binary tree with pairs at the leaves in such way that after replacing pair with new character and concating with the parent we got new pairs at the leaves up to the root - there are $n$ chatacters then $\frac{n}{2}$ pairs, then $\frac{n}{4}$, $\frac{n}{8}$, $\frac{n}{16}$... You see the pattern, there are $2n$ pairs, but according to algorithm description this yelds $\mathcal O(n\log n + n)$ time taking only input traversals.