In particular, Yuster and Zwick has a paper called "Finding Even Cycles Even Faster" which can find even cycles or output that that they don't exist in time $O(v^2)$.

Is there a easy way to calculate the asymptotics?

The calculations are simpler for the walks since the steps are independent and we can use local limit theorem. It is possible that the dependence of the steps in the pair of bridges might make the probability at bit smaller.

Yes sure, the hope is to get something similar to the result for a pair of random lattice walk. For such a pair of $n$ steps walk with $\alpha n$ positions taking the same steps, the probability that one walk is $c$-bounded given that the other is is $$\frac{c}{\sqrt{\pi(1-\alpha)\alpha n}}.$$