We can restate the question as: how many "fourth roots" does a given permutation have? That is, given a permutation $\sigma$, how many permutations $\tau$ exist such that $\tau^4 = \sigma$? The answer — let's call it $N(\sigma)$ — depends on the structure of $\sigma$.
(The basic idea of what to look at comes from section 4.8 of generatingfunctionology (e.g. here).)
Consider a permutation $\tau$, decomposed into cycles. For a particular cycle in $\tau$ of length $n$, let's look at what happens in $\tau^4$. If $(a_0, a_1, \dots...)$ is a cycle in $\tau$ (that is, $\tau$ takes $a_0$ to $a_1$, takes $a_1$ to $a_2$, etc.), then $\tau^4$ takes $a_0$ to $a_4$, takes $a_1$ to $a_5$, etc. The resulting (sub)permutation may be a single cycle or multiple cycles, depending upon $n$:
If $n$ is odd (relatively prime to $4$), then we have a single cycle of length $n$, which looks like $(a_0, a_4, a_8, \dots)$ with the indices looping around modulo $n$.
If $n$ is even but not a multiple of $4$, then we get two cycles of length $n/2$, one looking like $(a_0, a_4, a_8, \dots)$ and containing all the even indices, and the other looking like $(a_1, a_5, a_9 \dots)$ and containing all the odd ones.
If $n$ is a multiple of $4$, then we get four cycles of length $n/4$ each, namely $(a_0, a_4, \dots)$, $(a_1, a_5, \dots)$, $(a_2, a_6, \dots)$, and $(a_3, a_7, \dots)$.
Turning this around, we can look at a cycle of length $m$ in $\tau^4$ and say the following:
If $m$ is even, then it must have come, along with three others, as the result of a single cycle of length $4m$ splitting into four cycles of length $m$ each.
If $m$ is odd, then either:
One cycle of length $m$ gave rise to one cycle of length $m$,
One cycle of length $2m$ gave rise to two cycles of length $m$ each, or
One cycle of length $4m$ gave rise to four cycles of length $m$ each.
(This immediately gives a condition for $N(\sigma)$ to be positive, i.e. for the permutation $\sigma$ to have at least one fourth root: for every even number $m$, the number of cycles of length $m$ must be a multiple of $4$.)
We can now calculate $N(\sigma)$. For each number $m$, let the number of cycles of length $m$ in $\sigma$ be $c_m$. Then:
If $m$ is even, then ($c_m$ must be a multiple of $4$ and) we can reconstruct a list of $c_m/4$ original cycles of length $4m$ each, by picking $c_m/4$ ordered groups of four, with ordering among them and cyclic order within each group of four being irrelevant, the number of ways of doing which is $\frac{c_m!}{(c_m/4)!4^{c_m/4}}$ After picking a particular group of four cycles, we can make a big one out of them (find a fourth root of the product of these four cycles) by choosing where in the cyclic ordering we start in each of the four cycles. WLOG we can fix a point in the first cycle where we start so the choice is only among the other three, so we must multiply the above number by $m^3$.
If $m$ is odd, then for each integer partition of $c_m$ of the form $c_m = x + 2y + 4z$ with $x$, $y$ and $z$ being nonnegative integers, we can pick $x$ cycles of length $m$ by themselves, form $y$ pairs of cycles, and $z$ groups of four. The number of ways of doing this is $\frac{c_m!}{x! (y!2^y) (z!4^z)}.$ Again in each of the $y$ pairs we have $m$ ways of putting them together, and in each of the $z$ quadruplets we have $m^3$ ways of putting them together.
So using all that, the final expression for $N(\sigma)$ is:
$N(\sigma) = \left(\prod_{2|m}\frac{c_m!m^{3c_m/4}}{(c_m/4)!4^{c_m/4}}\right) \left(\prod_{2\not|m}\sum_{x,y,z:c_m=x+2y+4z}\frac{c_m! m^y m^{3z}}{x! (y!2^y) (z!4^z)}\right)$
I've checked this with a computer program for all permutations of size up to 12, so I'm finally convinced the expression is correct.
Examples: Consider your original permutation $\tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 1 & 3 & 6 & 4 & 5\end{pmatrix}$. We can write this in cycle notation as $\tau = (1 2) (3) (4 6 5)$. For this permutation, $\tau^4 = (1)(2)(3)(4 6 5)$. Notice how the cycle of length $2$ has split into two cycles of length $1$ each. If we want to start with this permutation $\sigma = (1)(2)(3)(4 6 5)$ and find fourth roots, we must look at the number of cycles $c_m$ for each $m$:
So the four fourth roots of \sigma = (1)(2)(3)(4 6 5) are
- (1)(2)(3)(4 6 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 2 & 3 & 6 & 4 & 5 \end{pmatrix},
- (1)(2 3)(4 6 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 3 & 2 & 6 & 4 & 5 \end{pmatrix},
- (2)(1 3)(4 6 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 2 & 1 & 6 & 4 & 5 \end{pmatrix},
- (3)(1 2)(4 6 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 1 & 3 & 6 & 4 & 5 \end{pmatrix}.
Let \sigma = (1 2 3)(4 5 6) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 3 & 1 & 5 & 6 & 4\end{pmatrix}$. We can either choose to keep the two $3$-cycles separate ($x = 2$, $y = 0$), giving us the root $(1 2 3)(4 5 6)$ itself, or we can choose to put the pair together ($x = 0, y = 1$), where the choice of the pair is unique but we can interleave the two in three ways — basically the form $(1 ? 3 ? 2 ?)$ with the '?'s filled by $(4 6 5)$ — giving us the roots $(1 4 3 6 2 5)$, $(1 5 3 4 2 6)$ and $(1 6 3 5 2 4). So we have four fourth roots.
Let \sigma = (1 2)(3 4)(5 6)(7 8 9)$. In this case for $m = 2$, $c_m = 3$ is not a multiple of $4$, so $N(\sigma) = 0.
Let \sigma = \begin{pmatrix}1 & 7\end{pmatrix} \begin{pmatrix}2\end{pmatrix} \begin{pmatrix}3 & 16 & 9\end{pmatrix} \begin{pmatrix}4 & 10\end{pmatrix} \begin{pmatrix}5\end{pmatrix} \begin{pmatrix}6 & 18\end{pmatrix} \begin{pmatrix}8\end{pmatrix} \begin{pmatrix}11 & 15 & 13\end{pmatrix} \begin{pmatrix}12 & 17\end{pmatrix} \begin{pmatrix}14\end{pmatrix}. Counting the fourth roots of this permutation by brute-force enumeration is impossible, but we can easily do it by collecting cycles of the same length:
For m = 1$: the roots of $\begin{pmatrix}2\end{pmatrix} \begin{pmatrix}5\end{pmatrix} \begin{pmatrix}8\end{pmatrix} \begin{pmatrix}14\end{pmatrix} are
- (all separate) \begin{pmatrix}2\end{pmatrix} \begin{pmatrix}5\end{pmatrix} \begin{pmatrix}8\end{pmatrix} \begin{pmatrix}14\end{pmatrix},
- (two pairs) \begin{pmatrix}2 & 5\end{pmatrix} \begin{pmatrix}8 & 14\end{pmatrix}$, $\begin{pmatrix}2 & 8\end{pmatrix} \begin{pmatrix}5 & 14\end{pmatrix}$, $\begin{pmatrix}2 & 14\end{pmatrix} \begin{pmatrix}5 & 8\end{pmatrix},
- (all together) \begin{pmatrix}2 & 5 & 8 & 14\end{pmatrix}$, $\begin{pmatrix}2 & 5 & 14 & 8\end{pmatrix}$, $\begin{pmatrix}2 & 8 & 5 & 14\end{pmatrix}$, $\begin{pmatrix}2 & 8 & 14 & 5\end{pmatrix}$, $\begin{pmatrix}2 & 14 & 5 & 8\end{pmatrix}$, $\begin{pmatrix}2 & 14 & 8 & 5\end{pmatrix}.
So there are 1 + 3 + 6 = 10$ roots of $\begin{pmatrix}2\end{pmatrix} \begin{pmatrix}5\end{pmatrix} \begin{pmatrix}8\end{pmatrix} \begin{pmatrix}14\end{pmatrix}.
For m = 2$, the roots of $\begin{pmatrix}1 & 7\end{pmatrix} \begin{pmatrix}4 & 10\end{pmatrix} \begin{pmatrix}6 & 18\end{pmatrix} \begin{pmatrix}12 & 17\end{pmatrix}$ are $6 \times 8 = 48$ in number (pick one of the $3!$ orderings of the last three, then one of the $2^3 orderings of each of the three).
For m = 3$, the roots of $\begin{pmatrix}3 & 16 & 9\end{pmatrix} \begin{pmatrix}11 & 15 & 13\end{pmatrix} are
- (both separate) \begin{pmatrix}3 & 16 & 9\end{pmatrix} \begin{pmatrix}11 & 15 & 13\end{pmatrix}
- (both together) \begin{pmatrix}3 & 11 & 9 & 13 & 16 & 15\end{pmatrix}$, $\begin{pmatrix}3 & 15 & 9 & 11 & 16 & 13\end{pmatrix}$, $\begin{pmatrix}3 & 13 & 9 & 15 & 16 & 11\end{pmatrix}.
So there are 1 + 3 = 4$ roots of $\begin{pmatrix}3 & 16 & 9\end{pmatrix} \begin{pmatrix}11 & 15 & 13\end{pmatrix}.
So totally N(\sigma) = 10 \times 48 \times 4 = 1920$.