diff --git a/remotefilelog/basestore.py b/remotefilelog/basestore.py
--- a/remotefilelog/basestore.py
+++ b/remotefilelog/basestore.py
@@ -1,6 +1,6 @@
 from __future__ import absolute_import
 
-import errno, hashlib, heapq, os, shutil, time
+import errno, hashlib, os, shutil, time
 
 from . import (
     constants,
@@ -69,14 +69,11 @@
         ui = self.ui
         entries = ledger.sources.get(self, [])
         count = 0
-        directories = set()
         for entry in entries:
             if entry.gced or (entry.datarepacked and entry.historyrepacked):
                 ui.progress(_("cleaning up"), count, unit="files",
                             total=len(entries))
                 path = self._getfilepath(entry.filename, entry.node)
-                dirpath = os.path.dirname(path)
-                directories.add((-len(dirpath), dirpath))
                 try:
                     os.remove(path)
                 except OSError as ex:
@@ -86,22 +83,6 @@
             count += 1
         ui.progress(_("cleaning up"), None)
 
-        # Clean up directories
-        cachepath = shallowutil.getcachepath(ui)
-        dirheap = list(directories)
-        heapq.heapify(dirheap)
-        seen = set([cachepath])
-        while dirheap:
-            length, dirpath = heapq.heappop(dirheap)
-            try:
-                os.rmdir(dirpath)
-                parent = os.path.dirname(dirpath)
-                if parent not in seen:
-                    seen.add(parent)
-                    heapq.heappush(dirheap, (-len(parent), parent))
-            except OSError:
-                pass
-
     # BELOW THIS ARE NON-STANDARD APIS
 
     def _getfiles(self):
diff --git a/remotefilelog/repack.py b/remotefilelog/repack.py
--- a/remotefilelog/repack.py
+++ b/remotefilelog/repack.py
@@ -439,9 +439,8 @@
             self.repackdata(ledger, targetdata)
             self.repackhistory(ledger, targethistory)
 
-            # Call cleanup on each source
-            for source in ledger.sources:
-                source.cleanup(ledger)
+            # Clean up
+            self.cleanup(ledger)
 
     def _chainorphans(self, ui, filename, nodes, orphans, deltabases):
         """Reorderes ``orphans`` into a single chain inside ``nodes`` and
@@ -677,6 +676,25 @@
         ui.progress(_("repacking history"), None)
         target.close(ledger=ledger)
 
+    def cleanup(self, ledger):
+        # Call cleanup on each source
+        for source in ledger.sources:
+            source.cleanup(ledger)
+
+        # Clean up leftover empty directories
+        cachepath = shallowutil.getcachepath(self.repo.ui)
+        for name in os.listdir(cachepath):
+            self._removeemptydirectories(os.path.join(cachepath, name))
+
+    def _removeemptydirectories(self, root):
+        if os.path.isdir(root):
+            paths = [os.path.join(root, name) for name in os.listdir(root)]
+            if all([self._removeemptydirectories(path) for path in paths]):
+                os.rmdir(root)
+                return True
+
+        return False
+
     def _toposort(self, ancestors):
         def parentfunc(node):
             p1, p2, linknode, copyfrom = ancestors[node]