Does the timing of cycle-walking pose a threat? Cycle-walking is a technique for format-preserving encryption that involves repeating an encryption process until the result is inside a desired range.

For example, given an input P, a range R, and an encryption function E.

C := E(P)
Is C in R?
  yes?
    Output C and quit
  no?
    C := E(C)
    Try again


My question is, does the variable timing of this pose a threat? It isn't constant time, but the time is dependant on E(P), which in theory shouldn't be a problem.
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.