Let $b = 1$ we have $f^a(1) + f(a)$ divides $2f(a)$. Hence, $2f(a) = C(f^a(1) + f(a))$, for some positive integer $C$. Thus, $C = 1$ and $f^a(1) = f(a)$. Whence, $f^a(b) = f^{a-1}(f(b)) = f^{a-1}(f^b(1)) = f^{a+b-1}(1) = f(a+b-1)$. By the same argument $f^b(a) = f(a+b-1)$. It then follows that $f(a+b-1)$ divides $f(ab) + b^2 - 1$. Interchanging $a, b$ to obtain $f(a+b-1) \mid b^2 - a^2$. Hence, $f(2a)$ divides $2a+1$. If the function is injective, it follows that
$$f^2(n) = f(f(n)) = f(n+1).$$
Hence $f(n) = n + 1$. This is indeed a solution. If the function is not injective then $f(r) = f(s)$ for some $r > s$. Thus, $f^r(1) = f^s(1)$. Hence, for each positive integer $m$; $f(m+r) = f^m(f^r(1)) = f^m(f^s(1)) = f(m+s)$. Hence, the function is periodic with a period of $r-s$. This implies that the function is indeed bounded. That is, for all $n$ we have $f(n) < M$. Choose a prime $p > M$ it follows that $f(p-1)$ divides $p$ and $f(p-1) < M < p$. Yielding $f(p-1) = 1$. Whence, for all large enough $p$; $f(p-1) = f^{p-1}(1) = 1$.
Let $d$ be the smallest positive integer such that $f^d(1) = 1$ by using the division algorithm, we can easily prove that $d$ divides $p-1$. This means that for all large enough $p$ we have $p \equiv 1 \pmod d$. This implies that $d \in \{1, 2\}$. Thus $f(f(1)) = 1$. Hence, $f(2k) = f^{2k}(1) = 1$ for all positive integers $k$. On the other hand, $f(2k+1) = f^{2k+1}(1) = f(1)$ for all non-negative integers $k$. Finally putting $a=b=2$ to obtain $f(1)$ divides $4$. Hence, $f(2k+1) \in \{1, 2, 4\}$. Whence, we have four functions satisfying the statement of the problem. $\blacksquare$