SICP - exercise 2.5 - representing pairs of nonnegative integers using only numbers and arithmetic operations
Well this is going to be inefficient no matter what, it's just that way. So we aren't going to improve the built-in expt, so that leaves repeat-divide for improvement. Let call it de-factor.

So first I thought something like

(define (de-factor p n)
 (let* ((max-expt (ceiling (/ (log p) (log n))))
             ;;log of p in base n
        (gcd-of (gcd p (expt n max-expt)))
        (res (/ (log gcd-of) (log n))))
   res))


which works so long as log internal is accurate enough to return the closest integer.It runs into significant rounding errors for some x and y less than a hundred.  If you built a very large log table you could solve in log time so long as you could accurately cast from your log table to the input x and y. (gcd runs in log time) Of course in such case the memory overhead of such a table or map would be huge, so not really that great of an optimization. 

(define (de-factor p n)
 (let* ((rough-max-expt (let loop ((x 1))
                           (if (&gt;= (expt n x) p) 
                               x
                               (loop (* 2 x)))))              
             ;;can't use log trick, returns inexact math
        (gcd-of (gcd p (expt n rough-max-expt))))
    (x-to-what-y n gcd-of)))

(define (x-to-what-y x n) ;return y such that (= n (expt x y)) is #t
 (if (= n 1)
     0
    (let loop ((y 1) (step 1) (acc x) (narrow? #f))
      (cond ((= acc n) y)
            ((&lt; step 1) (error x step acc narrow?))
            (else (let ((next (* acc (expt x step))))
                     (if (&lt;= next n)
                         (loop (+ y step) 
                               (if narrow? (/ step 2) (* step 2))
                               next
                               narrow?)
                         (loop y
                               (/ step 2)
                               acc
                               #t))))))))


Minimal changes to the rest

(define (cons x y)
    (* (expt 2 x) (expt 3 y)))


(define (car p) (de-factor p 2))

(define (cdr p) (de-factor p 3))


As far as performance it's still less than linear because of the exact bignum math. (cdr (cons 12345 54321)) returns 12345 in a few seconds, but (cdr (cons 123456 654321)) in about a minute and a half. 

When I tried your (cdr (car 12345 54321)) it ran out of memory, with a basic tail-recursion optimization, it took about 10 seconds. (cdr (cons 123456 654321)) is about a half hour. So my code is an optimization, but really just the nature of that big of numbers is they are very inefficient to do a lot of math on, and even more so the bigger they get. You would never do something this weird in production code. 

Tail optimization for benchmarking

(define (repeat-divide x y)
  (let loop ((acc 0) (x x))
    (if (&gt; (remainder x y) 0)
        acc
        (loop (+ 1 acc) (/ x y)))))