Does the timing of cycle-walking pose a threat?
Your intuition is correct: the timing channel in cycle walking does not affect the pseudorandom permutation (PRP) security of a format-preserving encryption scheme built using cycle walking. 

More precisely, it is possible to prove that any FPE scheme which meets PRP security in the standard sense also meets a stronger notion of PRP security in which the time taken to encrypt a point is given to the adversary. Intuitively, this is because the distribution of cycle lengths for a random permutation can be simulated given only the size of the domain. See section 9 of the original FPE paper.