it sounds like you want reduce
with update-in
i.e.
(defn new-map [f nested-vecs indices]
(reduce (fn [nv idxs] (update-in nv idxs f))
nested-vecs
indices))
;; I changed your inputs. Remember that indices start from 0
(new-map inc [[1 2 3] [4 5] [6] [7]] [[0 0] [1 1] [2 0]])
; => [[2 2 3] [4 6] [7] [7]]