diff --git a/mercurial/merge.py b/mercurial/merge.py
--- a/mercurial/merge.py
+++ b/mercurial/merge.py
@@ -653,23 +653,40 @@
         and repo.dirstate.normalize(f) not in repo.dirstate
         and mctx[f2].cmp(wctx[f]))
 
-def _checkunknowndirs(repo, f):
+def _checkunknowndirs(repo, f, unknowndircache, missingdircache):
     """
     Look for any unknown files or directories that may have a path conflict
     with a file.  If any path prefix of the file exists as a file or link,
     then it conflicts.  If the file itself is a directory that contains any
     file that is not tracked, then it conflicts.
 
+    `unknowndircache` is a set of paths known to be good.  This prevents
+    repeated checking of dirs.  It will be updated with any new dirs that
+    are checked and found to be safe.
+
+    `missingdircache` is a set of paths that are known to be absent.  This
+    prevents repeated checking of subdirectories that are known not to exist.
+    It will be updated with any new dirs that are checked and found to be
+    absent.
+
     Returns the shortest path at which a conflict occurs, or None if there is
     no conflict.
     """
 
     # Check for path prefixes that exist as unknown files.
     for p in reversed(list(util.finddirs(f))):
-        if (repo.wvfs.audit.check(p)
-                and repo.wvfs.isfileorlink(p)
-                and repo.dirstate.normalize(p) not in repo.dirstate):
-            return p
+        if p in missingdircache:
+            return
+        if p in unknowndircache:
+            continue
+        if repo.wvfs.audit.check(p):
+            if (repo.wvfs.isfileorlink(p)
+                    and repo.dirstate.normalize(p) not in repo.dirstate):
+                return p
+            if not repo.wvfs.lexists(p):
+                missingdircache.add(p)
+                return
+            unknowndircache.add(p)
 
     # Check if the file conflicts with a directory containing unknown files.
     if repo.wvfs.audit.check(f) and repo.wvfs.isdir(f):
@@ -700,12 +717,15 @@
             elif config == 'warn':
                 warnconflicts.update(conflicts)
 
+        unknowndircache = set()
+        missingdircache = set()
         for f, (m, args, msg) in actions.iteritems():
             if m in ('c', 'dc'):
                 if _checkunknownfile(repo, wctx, mctx, f):
                     fileconflicts.add(f)
                 elif f not in wctx:
-                    path = _checkunknowndirs(repo, f)
+                    path = _checkunknowndirs(repo, f,
+                                             unknowndircache, missingdircache)
                     if path is not None:
                         pathconflicts.add(path)
             elif m == 'dg':