Can the non-existence of absolute complements be proved without using the axiom of unions?

The axioms of Pairing and Separation are enough to reproduce Russell's Paradox indirectly:

Suppose for a contradiction that there are $A \cup B = \mathbf V$ and $A\cap B=\varnothing$.

Let $x\in\!\!\in y$ be an abbreviation for $\exists z(x\in z\land z\in y)$ and consider $$ A' = \{x\in A\mid \neg(x\in\!\!\in x)\} \qquad B' = \{x\in B\mid \neg(x\in\!\!\in x)\} $$ and let $P=\{A',B'\}$.

Assume without loss of generality that $P \in A$, $P\notin B$ (otherwise just swap $A$ and $B$).

Now if $P\in A'$ then $P\in A'\in P$, so $P$ should not have been in $A'$.

Therefore $P\notin A'$, but this requires that $P\in\!\!\in P$, or in other words $P$ is an element of one of its two elements. But we just concluded $P\notin A'$, and $P\notin B'$ because $P\notin B$.

Either way we have a contradiction.

Yes; you can prove this from just Pairing and Regularity. Suppose $X$ is a set and the complement $Y$ of $X$ is also a set. By Pairing, $\{X\}$, $\{Y\}$, and $\{X,Y\}$ are sets. Regularity for $\{X\}$ says that $X\not\in X$ and Regularity for $\{Y\}$ says that $Y\not\in Y$. Since $X$ and $Y$ are complements, $X\in Y$ and $Y\in X$. But this now violates Regularity for $\{X,Y\}$.