diff --git a/mercurial/scmutil.py b/mercurial/scmutil.py
--- a/mercurial/scmutil.py
+++ b/mercurial/scmutil.py
@@ -733,8 +733,9 @@ def addremove(repo, pats=[], opts={}, dr
     rejected = []
     m.bad = lambda x, y: rejected.append(x)
 
-    for abs in repo.walk(m):
-        target = repo.wjoin(abs)
+    ctx = repo[None]
+    walkresults = repo.dirstate.walk(m, sorted(ctx.substate), True, False)
+    for abs in sorted(walkresults):
         good = True
         try:
             audit_path(abs)
@@ -743,14 +744,15 @@ def addremove(repo, pats=[], opts={}, dr
         rel = m.rel(abs)
         exact = m.exact(abs)
 
+        st = walkresults[abs]
         dstate = repo.dirstate[abs]
         if good and dstate == '?':
             unknown.append(abs)
             if repo.ui.verbose or not exact:
                 repo.ui.status(_('adding %s\n') % ((pats and rel) or abs))
         elif (dstate != 'r' and
-              (not good or not os.path.lexists(target) or
-               (os.path.isdir(target) and not os.path.islink(target)))):
+              (not good or not st or
+               (stat.S_ISDIR(st.st_mode) and not stat.S_ISLNK(st.st_mode)))):
             deleted.append(abs)
             if repo.ui.verbose or not exact:
                 repo.ui.status(_('removing %s\n') % ((pats and rel) or abs))