Are we talking about the Darcs version < 2 merge algorithm or the merge algorithm in current darcs?
For the sake of completeness, I don't know the full story for the complexity of Darcs "in most cases", but I believe it to be linear in the size of history in the normal case (as it needs to try and commute all the patches with your new patch).