Here are my thoughts:
letfn instead of let
You could use letfn instead of let, which would be a little more concise:
(letfn [(update-or-add [m1 k f arg]
...
conj vs. update-in
conj and update-in are very similar functions in that they both take a map and "update" the value for a key that may or may not exist. Because of this, they are sometimes exchangeable. update-in is fine here, but I think using conj for both scenarios could make it easier to see at a glance what your function is doing. (See the next example.)
if-let
The (let [x (get m1 k)] (if (nil? x) ... part of your code is a good example of where if-let comes in handy.
(if-let [x (m1 k)]
(conj m1 {k (f x arg)})
(conj m1 {k arg}))
Which you could even simplify further by moving the if-let inside of a single conj function call:
(conj m1 {k (if-let [x (m1 k)] (f x arg) arg)})
As an aside, I tend to prefer assoc, although it's really just as good as conj:
(assoc m1 k (if-let [x (m1 k)] (f x arg) arg))
Reducers work best as functions taking 2 arguments
The first thing I noticed about your loop is that its arguments can be simplified:
(loop [m1 m, ms ms]
...
Essentially what you're doing is starting with m1 and reducing update-or-add over each key-value pair in each map in ms. The tricky thing here is that, as you pointed out, this is a nested reducing operation, in that each map in ms can have multiple key-value entries. You have the right general idea in that you have a reduce within a loop, but a better/simpler way to do this would be to make your update-or-add function take the two arguments that a reducing function expects -- an accumulator and the next item in the collection being reduced over. Once you have update-or-add working that way, you can do the same thing with your loop and at that point you'll be able to represent your solution as a simple nested reduce.
Let's start with update-or-add. This function takes a working "map in progress" and a key-value pair and either adds it to the map if that key isn't already there, or it updates the value to be the result of calling f with the value already there and the new value as arguments. Note that we don't need to make f an argument because it's already available within the context of the entire function merge-with2. You can also use destructuring to easily access the key and the value of the key-value pair.
(letfn [(update-or-add [m1 [k v]]
(assoc m1 k (if-let [x (m1 k)]
(f x v)
v)))]
...
Now you can use update-or-add "as-is" within a reduce.
You can do something similar with your main loop. To simplify things, let's make it its own function, and call it something like merge-with-one. This function will take one of the maps supplied to merge-with2 and reduce update-or-add over its key-value pairs. Defining this function is actually super easy, because it's just a call to reduce. So, here is my suggested refactoring of your code:
(fn merge-with2 [f m & ms]
(letfn [(update-or-add [m1 [k v]]
(assoc m1 k (if-let [x (m1 k)]
(f x v)
v)))
(merge-with-one [m1 m2]
(reduce update-or-add m1 m2))]
(reduce merge-with-one m ms)))
It turns out that this is actually pretty close to the actual implementation of merge-with in clojure.core.
