$\newcommand{\ran}{\operatorname{ran}}$Here’s one way to think about it. Suppose that $y\in\ran f$; then we can pull $y$ back to $f^{-1}(y)\in X$. If $f^{-1}(y)\in\ran g$, we can pull it back to $g^{-1}(f^{-1}(y))\in Y$. If we continue this pulling back, one of two things must happen: either we reach a dead end at a point of $X$ or $Y$ that can’t be pulled back (because it’s in $Y\setminus\ran f$ or $X\setminus\ran g$), or we don’t.
Let $X_0=X\setminus\ran g$, the set of points of $X$ that cannot be pulled back at all, and let $Y_0=Y\setminus\ran f$. More generally, for each $n\in\omega$ let $X_n$ be the set of points of $X$ that can be pulled back exactly $n$ times, and let $Y_n$ be the set of points of $Y$ that can be pulled back exactly $n$ times. Finally, let $X_\omega$ and $Y_\omega$ by the subsets of $X$ and $Y$, respectively whose points can be pulled back infinitely many times.
At this point a sketch helps; it should show the partitions $\{X_n:n\le\omega\}$ of $X$ and $\{Y_n:n\le\omega\}$ of $Y$, and it should include arrows indicating what parts of $X$ get mapped to what parts of $Y$ and vice versa. To avoid having arrows crossing, I’ve taken $X$ and $Y$ apart in the following diagram.
$$\begin{array}{}
X_0&\overset{f}\longrightarrow&Y_1&\overset{g}\longrightarrow&X_2&\overset{f}\longrightarrow& Y_3&\overset{g}\longrightarrow&X_4&\dots&X_\omega\\
Y_0&\overset{g}\longrightarrow&X_1&\overset{f}\longrightarrow&Y_2&\overset{g}\longrightarrow&X_3&\overset{f}\longrightarrow&Y_4&\dots&Y_\omega
\end{array}$$
Each of the arrows is a bijection, so I can break up the diagram into $\omega$ self-contained parts. The first two parts are:
$$\begin{array}{}
X_0&\overset{f}\longrightarrow&Y_1\\
Y_0&\overset{g}\longrightarrow&X_1
\end{array}\qquad
\begin{array}{}
X_2&\overset{f}\longrightarrow&Y_3\\
Y_2&\overset{g}\longrightarrow&X_3
\end{array}$$
Ignoring $X_\omega$ and $Y_\omega$ for the moment, I can rearrange the rest of the diagram to give my a bijection from $X\setminus X_\omega$ to $Y\setminus Y_\omega$:
$$\begin{array}{ccc}
X_0&\overset{f}\longrightarrow&Y_1\\
X_1&\overset{g^{-1}}\longrightarrow&Y_0\\
X_2&\overset{f}\longrightarrow&Y_3\\
X_3&\overset{g^{-1}}\longrightarrow&Y_2\\
\vdots&\vdots&\vdots\\
X_{2k}&\overset{f}\longrightarrow&Y_{2k+1}\\
X_{2k+1}&\overset{g^{-1}}\longrightarrow&Y_{2k}\\
\vdots&\vdots&\vdots
\end{array}$$
Finally, I claim that $f[X_\omega]=Y_\omega$: everything in $X_\omega$ can be pulled back infinitely often, so everything in $f[X_\omega]$ can be pulled back infinitely often, and therefore $f[X_\omega]\subseteq Y_\omega$. On the other hand, if $y\in Y_\omega$, then $y$ can be pulled back infinitely often, so it must be possible to pull $f^{-1}(y)$ back infinitely often, and therefore $f^{-1}(y)\in X_\omega$. Thus, $Y_\omega\subseteq f[X_\omega]$ as well. The diagram above can now be completed to show a bijection from $X$ onto $Y$:
$$\begin{array}{ccc}
X_0&\overset{f}\longrightarrow&Y_1\\
X_1&\overset{g^{-1}}\longrightarrow&Y_0\\
X_2&\overset{f}\longrightarrow&Y_3\\
X_3&\overset{g^{-1}}\longrightarrow&Y_2\\
\vdots&\vdots&\vdots\\
X_{2k}&\overset{f}\longrightarrow&Y_{2k+1}\\
X_{2k+1}&\overset{g^{-1}}\longrightarrow&Y_{2k}\\
\vdots&\vdots&\vdots\\
X_\omega&\overset{f}\longrightarrow&Y_\omega
\end{array}$$
The bijection is defined piecewise, but that’s no problem.
There are a few details to be filled in to make this a fully rigorous proof, but I think that it does give a reasonable idea of one possible intuition.
Added: Here’s a very rough sketch. Arrows from left to right are (parts of) $f$, and arrows from right to left are (parts of) $g$.
Best Answer
The equality does not hold: as you've stated, it could be that $\bigcap A_n$ is nonempty. However, we can show that there is a bijection between $A_0$ and $B$ using this idea. Consider the following picture of the situation:
We see there are three types of regions: the region $\mathcal A=\bigcup A_n\setminus B_n$ (yellow), the region $\mathcal B=\bigcup B_n\setminus A_{n+1}$ (blue), and then the remaining elements, $\mathcal C=\bigcap A_n=\bigcap B_n$ (grey).
Note that $A_0\supseteq B_0\supseteq A_1\supseteq B_1\dots\supseteq\mathcal C$.
We define a map $h:A_0\to B$ by letting
\begin{align} h:x\mapsto\begin{cases} f(x)&x\in\mathcal A\\ x&x\in \mathcal B\cup\mathcal C \end{cases} \end{align}
Clearly $h$ is a bijection on $\mathcal B\cup\mathcal C$, since it is the identity function. Since $B=B_0=\mathcal B\cup \mathcal C\cup (\mathcal A\setminus (A_0\setminus B_0))$ (i.e. the set $A_0$ without its outer ring), all we have left to show is that $h$ is also a bijection from $\mathcal A$ to $\mathcal A\setminus(A_0\setminus B_0)$.
I claim that $f\restriction (A_n\setminus B_n)$ is a bijection between $A_n\setminus B_n\to A_{n+1}\setminus B_{n+1}$ for all $n$. It follows from this that $f\restriction \mathcal A$ is a bijection from $\mathcal A\to \mathcal A\setminus (A_0\setminus B_0)$, and thus that $h$ is a bijection $A_0\to B$. Clearly since $f$ is injective, its restriction is also injective.
Let $x\in A_{n}\setminus B_n$, then $f(x)\notin B_{n+1}$, since $f[B_n]=B_{n+1}$ and $x\notin B_n$ and $f$ is injective. Since $x\in A_n$, we see that $f(x)\in A_{n+1}=f[A_n]$. Therefore $f[A_n\setminus B_n]\subset A_{n+1}\setminus B_{n+1}$.
Finally $f\restriction A_n\setminus B_n$ maps surjectively to $A_{n+1}\setminus B_{n+1}$: if $y\in A_{n+1}\setminus B_{n+1}$, then $f^{-1}(y)\in A_n$. We also see $f^{-1}(y)\notin B_{n}$, since $f[B_n]=B_{n+1}$.