As @JetfiRex pointed out in the comments, this can be translated into a problem of counting the number of Eulerian cycles of a directed graph.
Let $V=\{ a_i \} = \{b_i\}$ be the set of all elements which appear in the sequences $a$ and $b$. Let $E = \{ a_i \overset{i}{\leftarrow} b_i\ |\ 1 \leq i \leq n \}$ denote the mappings (i.e. labeled directed edges) between the initial and final values of each position in the sequences. Any cycle for the graph $G=(V,E)$ (i.e. a walk through the graph which traverses each edge once) is a valid permutation which relates $a$ and $b$. For example, for the sequences $$ a = (\alpha,\alpha,\beta,\beta,\beta,\gamma) \qquad b = (\alpha,\beta,\beta,\gamma,\beta,\alpha) $$ the associated graph is
The cycle as $\beta \rightarrow\alpha\rightarrow\gamma\rightarrow\beta$ corresponds to the permutation $(264)$ and the cycle $\beta\rightarrow\alpha\rightarrow\alpha\rightarrow\gamma\rightarrow\beta$ corresponds to the permutation $(21643)$.
The Eulerian cycles of this graph are all the $n$-cycle permutations which take $a$ to $b$. We can calculate the number of Eulerian cycles using the BEST theorem
$$\tag{1}\label{1} \operatorname{ec}(G) = t_w(G) \prod_{v\in V} \bigl(\deg(v)-1\bigr)! $$ where $t_w(G)$ is the number of arborescences and $\deg(v)$ is the indegree of vertex $v$. We can use Kirchhoff's theorem to calculate $t_w(g)$. We construct the graph's Laplacian matrix $Q=D-A$, where $D$ is the degree matrix of the graph (the diagonal matrix of vertex indegrees) and $A$ is the (weighted) adjacency matrix. We then have that $$\tag{2} t_w(G) = \det(Q^*) $$ where $t_w(G)$ is the first cofactor of $Q$, which is the determinant of the matrix $Q^*$ formed by removing the first row and column of $Q$.
In order to calculate all of the $k$-cycle permutations, we need to find paths of length $k$ rather than of length $n$. We can do this by looking at all the subgraphs formed by removing $(n-k)$ self-loops from the graph $G$. For the example sequences $a$ and $b$, the subgraphs for $k=4$ permutations are those where two self-loops have been removed:
Thus, we just need to apply $\eqref{1}$ to each of these graphs and add up the number of Eulerian paths. First, we can note that $Q$, and thus $t_W(G)$, is independent of the number of self-loops, since the indegree minus self-adjacency (the diagonal of $Q$) is equal to the indegree from non-self-loops. From this, we can calculate the total number of $k$-cycles: $$\tag{3}\label{3} N_k(a,b) = t_w\left(G(a,b)\right) \sum_{p\ \vdash\ (n-k)}\ \prod_{v\in V(a,b)} \binom{l_v}{p_v}(\deg(v)-p_v-1)! $$
First, we have factored $t_w(G)$ from the BEST theorem. Next, we sum over all ways of removing $p_v$ self-loops from vertex $v$, subject to the constraint that $\sum_v p_v = (n-k)$. For each vertex, we have $\binom{l_v}{p_v}$ ways of choosing which of the $l_v$ self-loops to remove (since they are labeled/distinguishable); if $p_v > l_v$ we take $\binom{l_v}{p_v}=0$. Finally, the degree of the vertex after removing $p_v$ self-loops is $(\deg(v)-p_v)$.
In the case that $G$ is not connected, then in order to have a $k$-cycle, the total number of $k$-cycles is simply the sum of \eqref{3} for each connected component. This points to a possible generalization I have not yet proven, which is that for a generic $(k_1,k_2,\ldots)$-cycle permutation, the number of permutations is the product of the $N_{k_i}$ calculated for the $i$th connected component of $G$. In that case, the number of $(4,2)$-cycle permutations would be the number of $k=4$ permutations on the first connected component times the number of $k=2$ permutations on the second connected component, plus the number of $k=4$ permutations on the second connected component times the number of $k=2$ permutations on the first connected component.
