Common Lisp - Abstract the (duplicate?) behavior between “sort” and “replace”

I have written these two functions that have a similar process. The first is meant to "split" a string on a given character and the second is meant to "replace-all" instances of a character in a given string. The behavior between the two seems very similar - can you think of a good way to abstract that behavior into a third, reusable, function? (which could be executed by calling, for example, (where-found sought-letter searchee-string thing-to-do))

(defun split (separator splittee)
  (let ((next-index (position separator splittee)))
    (if next-index
      (cons (subseq splittee 0 next-index) (split separator (subseq splittee (1+ next-index))))
      (list splittee))))

(defun replace-all (replacand replacee replacor)
  (let ((next-index (position replacand replacee)))
    (if next-index
      (concatenate 'string (subseq replacee 0 next-index) replacor (replace-all replacand (subseq replacee (1+ next-index)) replacor))
      replacee)))

UPDATE: The following is roughly what I am trying to do, though it is still not working correctly (debugging help would be great too)

EDIT: I have it working now. What do you think? Is this better than the original code, or is it too complicated?

(defun where-found (sought-letter the-string to-do-onroute to-do-on-leaf)
  (let ((next-index (position sought-letter the-string)))
    (if next-index
      (apply to-do-onroute
         (list (subseq the-string 0 next-index) 
           (subseq the-string (1+ next-index))))
      (apply to-do-on-leaf (list the-string))))) 

(defun split (separator splittee)
  (where-found separator splittee 
           (lambda (pre-string post-string) (cons pre-string (split separator post-string))) 
           (lambda (leaf-string) (list leaf-string))))

(defun replace-all (to-be-replaced-string the-patient-string the-replacement-string)
  (where-found to-be-replaced-string the-patient-string 
           (lambda (pre-string post-string) 
         (format t "pre: ~a post: ~a the-replacement-string: ~a ~%" pre-string post-string the-replacement-string) 
         (concatenate 'string pre-string the-replacement-string (replace-all to-be-replaced-string post-string the-replacement-string)))
           (lambda (leaf-string) leaf-string)))

(format t "the cat is here: ~a ~%" (replace-all #\Space "the cat is here" ""))
(format t "the cat is here: ~a ~%" (split #\Space "the cat is here"))

UPDATE: Based on the feedback I have received, I have revised to the following. Thanks for your help!

(defun replace-all (seq from to) (map (type-of seq) (lambda (it) (if (equal it from) to it)) seq))
(defun split (seq on) 
  (let ((next (position on seq))) 
    (if next (cons (subseq seq 0 next) (split (subseq seq (1+ next)) on)) (list seq))))

(format t "~a ~%" (replace-all "happy birthday" #\p #\t))
(format t "~a ~%" (split "happy birthday" #\Space))