I will assume that $\Gamma$ is regular of degree $1$ (so $n=2m$ for some $m$.) You say that you don't care specifically about the uniform distribution on $S_n=S_{2m}.$ However I will deal mainly with that case. At the end I'll argue that your weaker condition might lead to about the same results, but that is a guess.

$\Gamma$ has $2m$ vertices and $m$ edges. Imagine they are red. Also $\Gamma^{\pi}$ has $m$ edges, imagine they are green. Then in $G= \Gamma \cup \Gamma^{\pi},$ each vertex is on one edge of each color so $G$ is the union of one or more even length cycles (including the possibility of a digon, a cycle of length $2$ with two points and two edges, one of each color.)

Consider these probabilities

After some work it turns out that, for $t=m-k,$

$$p_m(k)=\frac1{2m-1}\frac{\binom{2t}t}{2^{2t}}\frac{2^{2m-2}}{\binom{2m-2}{m-1}}$$

Also, for $\frac{m}2 \lt k \leq m,$ $$q_m(k)=\frac{mp_m(k)}k.$$

I have nice proofs for these formulas. They show good agreement with the results of random computations.

**simulation details**

I did $100,000$ trials with $m=15.$ The expected numbers (out of $10^5$) with longest cycle of length at least $16,18,\cdots,30$ are the first line below. The second is the actual values from the trial:

$$89290, 80228, 71553, 63035, 54432, 45418, 35435, 23074$$

$$89211, 80202, 71542, 63137, 54448, 45530, 35359, 23062$$

In particular, the probability that $G$ is connected is $$p_m(m)=\frac{2^{2m-2}}{(2m-1)\binom{2m-2}{m-1}} \approx \sqrt{\frac{\pi}{4m}}. $$

For $t=m-k$ not too small, $$p_m(k) \sim \frac{\sqrt{\frac{m}t}}{2m-1}.$$

I would expect, for reasons given in a moment, that the probability that the longest cycle is at least $ 2m\rho$ (for $\rho \gt \frac12$) should converge to a limit.

Here are the calculated probabilities to be above $ 2m\rho$ for $\rho=0.5,0.6,0.7,0.8,0.9.$ The first line is for $m=200$ and the next for $m=400:$

$$.70666, .63186, .54692, .44610, .31445$$
$$.70689, .63216, .54732, .44665, .31534$$

The reason I suspected this was that (as is well known) for a random permutation of $X$ , a set of size $n,$ one has probability that the cycle of $x$ has length $k$ is independent of $k:$ $$p_n(k)=\frac1n$$ and the probability that the longest cycle has length $k$ is (for $\frac{n}2 \lt k \leq n$) is independent of $n:$
$$q_n(k)=\frac1k$$

So the probability that the longest cycle has length at least $j=\rho n \gt \frac{n}2$ is $$\sum_{k=j}^n\frac1k \sim -\ln{\rho}.$$

**Regarding random permutations**

Certainly, saying that each permutation is chosen with probability $\frac{1+\varepsilon}{n!}$ with $|\varepsilon|$ sufficiently small will satisfy your condition (essentially, this is just your condition for $k=n.$). I wonder if the converse is true?

I guess, under that assumption, the results for $\Gamma \cup \Gamma^{\pi}$ (such as they are) would stay pretty much the same. It might be delicate Perhaps it would be worth studying the simpler problem of cycles in $S_n$ under that variation.

In a (now hidden) comment you describe the process of a random walk on a connected Cayley Graph for $S_n$. This does converge rapidly to the uniform distribution (the metric being $\sum_{S_n}|p(\pi)-\frac1{n!}|.$ Certainly some choices converge faster than others but it is (after a while) an exponential decay.

As you may know, Persi Diaconis has nice results for this. An easy overview is here with more detailed results easy to find. If we have an $n! \times n!$ matrix where each row has all entries $0$ except that $k$ of them are $\frac1k$ then no power will have all entries $\frac1{n!}.$ However there are strong stopping rules (such as wait until a certain event occurs, then do one more multiplication) which, if followed, will eventually give the uniform distribution. We can't say what the stopping time is, there is a minute chance that it is huge, but I recall results such as "the stopping time is almost surely less than $\frac32 n log_2 n.$"

7more comments