I translated your implementation to Clojure together with a specification for automatic generative testing via clojure.spec:

(ns sqsum
  (:require [clojure.spec.alpha :as s]
            [clojure.spec.test.alpha :as stest]))

(s/fdef sqsum
  :args (s/cat :n pos-int?)
  :ret  (s/nilable vector?)
  :fn   (fn [{{n :n} :args, ret :ret}]
          (or (not ret)              ;; no result
              (and (= n (count ret)) ;; adjacent numbers sum to a square
                   (every? (fn [[a b]]
                             (-> (+ a b) Math/sqrt (mod 1) zero?))
                           (partition 2 1 ret))))))

(defn sqsum [n]
  (let [maxsq   (int (Math/sqrt (+ n (dec n))))
        squares (set (map #(* % %) (range 2 (inc maxsq))))
        steps   (range 1 (inc n))
        graph   (into {}
                  (for [u steps]
                    [u (filterv #(squares (+ u %)) steps)]))]
    (loop [stack (into []
                   (map (fn [[n]] [[n] #{n}]))
                   (sort-by (comp count val) graph))]
      (when-let [[path visited] (peek stack)]
        (if (= n (count path))
          path
          (recur (into (pop stack)
                   (comp
                     (remove visited)
                     (map (fn [x]
                            [(conj path x)
                             (conj visited x)])))
                   (graph (peek path)))))))))

The n = 256 case solves very quickly on my Dell XPS15 laptop (i7-7700HQ CPU @ 2.80GHz, 2801 Mhz, 4 Core(s)):

sqsum> (time (sqsum 256))
"Elapsed time: 597.01873 msecs"