--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -696,29 +696,38 @@ var Bookmarks = Object.freeze({
   eraseEverything(options = {}) {
     if (!options.source) {
       options.source = Bookmarks.SOURCES.DEFAULT;
     }
 
     const folderGuids = [this.toolbarGuid, this.menuGuid, this.unfiledGuid,
                           this.mobileGuid];
     return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: eraseEverything",
-      db => db.executeTransaction(async function() {
-        await removeFoldersContents(db, folderGuids, options);
-        const time = PlacesUtils.toPRTime(new Date());
-        const syncChangeDelta =
-          PlacesSyncUtils.bookmarks.determineSyncChangeDelta(options.source);
-        for (let folderGuid of folderGuids) {
-          await db.executeCached(
-            `UPDATE moz_bookmarks SET lastModified = :time,
-                                      syncChangeCounter = syncChangeCounter + :syncChangeDelta
-             WHERE id IN (SELECT id FROM moz_bookmarks WHERE guid = :folderGuid )
-            `, { folderGuid, time, syncChangeDelta });
+      async function(db) {
+        let urls;
+
+        await db.executeTransaction(async function() {
+          urls = await removeFoldersContents(db, folderGuids, options);
+          const time = PlacesUtils.toPRTime(new Date());
+          const syncChangeDelta =
+            PlacesSyncUtils.bookmarks.determineSyncChangeDelta(options.source);
+          for (let folderGuid of folderGuids) {
+            await db.executeCached(
+              `UPDATE moz_bookmarks SET lastModified = :time,
+                                        syncChangeCounter = syncChangeCounter + :syncChangeDelta
+               WHERE id IN (SELECT id FROM moz_bookmarks WHERE guid = :folderGuid )
+              `, { folderGuid, time, syncChangeDelta });
+          }
+        });
+
+        // We don't wait for the frecency calculation.
+        if (urls && urls.length) {
+          updateFrecency(db, urls, true).then(null, Cu.reportError);
         }
-      })
+      }
     );
   },
 
   /**
    * Returns a list of recently bookmarked items.
    * Only includes actual bookmarks. Excludes folders, separators and queries.
    *
    * @param {integer} numberOfItems
@@ -1536,25 +1545,26 @@ function fetchBookmarksByParent(info) {
   });
 }
 
 // Remove implementation.
 
 function removeBookmark(item, options) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: removeBookmark",
     async function(db) {
+    let urls;
     let isUntagging = item._grandParentId == PlacesUtils.tagsFolderId;
 
     await db.executeTransaction(async function transaction() {
       // If it's a folder, remove its contents first.
       if (item.type == Bookmarks.TYPE_FOLDER) {
         if (options.preventRemovalOfNonEmptyFolders && item._childCount > 0) {
           throw new Error("Cannot remove a non-empty folder.");
         }
-        await removeFoldersContents(db, [item.guid], options);
+        urls = await removeFoldersContents(db, [item.guid], options);
       }
 
       // Remove annotations first.  If it's a tag, we can avoid paying that cost.
       if (!isUntagging) {
         // We don't go through the annotations service for this cause otherwise
         // we'd get a pointless onItemChanged notification and it would also
         // set lastModified to an unexpected value.
         await removeAnnotationsForItem(db, item._id);
@@ -1591,16 +1601,20 @@ function removeBookmark(item, options) {
     });
 
     // If not a tag recalculate frecency...
     if (item.type == Bookmarks.TYPE_BOOKMARK && !isUntagging) {
       // ...though we don't wait for the calculation.
       updateFrecency(db, [item.url]).catch(Cu.reportError);
     }
 
+    if (urls && urls.length && item.type == Bookmarks.TYPE_FOLDER) {
+      updateFrecency(db, urls, true).catch(Cu.reportError);
+    }
+
     return item;
   });
 }
 
 // Reorder implementation.
 
 function reorderChildren(parent, orderedChildrenGuids, options) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: updateBookmark",
@@ -1945,20 +1959,25 @@ var setAncestorsLastModified = async fun
       WHERE guid = :guid`,
       { guid: folderGuid, syncChangeDelta });
   }
 };
 
 /**
  * Remove all descendants of one or more bookmark folders.
  *
- * @param db
+ * @param {Object} db
  *        the Sqlite.jsm connection handle.
- * @param folderGuids
+ * @param {Array} folderGuids
  *        array of folder guids.
+ * @return {Array}
+ *         An array of urls that will need to be updated for frecency. These
+ *         are returned rather than updated immediately so that the caller
+ *         can decide when they need to be updated - they do not need to
+ *         stop this function from completing.
  */
 var removeFoldersContents =
 async function(db, folderGuids, options) {
   let syncChangeDelta =
     PlacesSyncUtils.bookmarks.determineSyncChangeDelta(options.source);
 
   let itemsRemoved = [];
   for (let folderGuid of folderGuids) {
@@ -2003,19 +2022,16 @@ async function(db, folderGuids, options)
   // folders.
   await addSyncChangesForRemovedTagFolders(db, itemsRemoved, syncChangeDelta);
 
   // Cleanup orphans.
   await removeOrphanAnnotations(db);
 
   // TODO (Bug 1087576): this may leave orphan tags behind.
 
-  let urls = itemsRemoved.filter(item => "url" in item).map(item => item.url);
-  updateFrecency(db, urls, true).then(null, Cu.reportError);
-
   // Send onItemRemoved notifications to listeners.
   // TODO (Bug 1087580): for the case of eraseEverything, this should send a
   // single clear bookmarks notification rather than notifying for each
   // bookmark.
 
   // Notify listeners in reverse order to serve children before parents.
   let { source = Bookmarks.SOURCES.DEFAULT } = options;
   let observers = PlacesUtils.bookmarks.getObservers();
@@ -2035,16 +2051,17 @@ async function(db, folderGuids, options)
         notify(observers, "onItemChanged", [ entry._id, "tags", false, "",
                                              PlacesUtils.toPRTime(entry.lastModified),
                                              entry.type, entry._parentId,
                                              entry.guid, entry.parentGuid,
                                              "", source ]);
       }
     }
   }
+  return itemsRemoved.filter(item => "url" in item).map(item => item.url);
 };
 
 /**
  * Tries to insert a new place if it doesn't exist yet.
  * @param url
  *        A valid URL object.
  * @return {Promise} resolved when the operation is complete.
  */

--- a/toolkit/components/places/tests/bookmarks/test_bookmarks_remove.js
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_remove.js
@@ -169,47 +169,72 @@ add_task(async function remove_bookmark_
 });
 
 add_task(async function remove_folder() {
   let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
                                                  type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                  title: "a folder" });
   checkBookmarkObject(bm1);
 
-  let manyFrencenciesPromise = promiseManyFrecenciesChanged();
-
   let bm2 = await PlacesUtils.bookmarks.remove(bm1.guid);
   checkBookmarkObject(bm2);
 
   Assert.deepEqual(bm1, bm2);
   Assert.equal(bm2.parentGuid, PlacesUtils.bookmarks.unfiledGuid);
   Assert.equal(bm2.index, 0);
   Assert.deepEqual(bm2.dateAdded, bm2.lastModified);
   Assert.equal(bm2.type, PlacesUtils.bookmarks.TYPE_FOLDER);
   Assert.equal(bm2.title, "a folder");
   Assert.ok(!("url" in bm2));
 
-  // We should get an onManyFrecenciesChanged notification with the remove of
-  // a folder.
+  // No promiseManyFrecenciesChanged in this test as the folder doesn't have
+  // any children that would need updating.
+});
+
+add_task(async function test_contents_removed() {
+  let folder1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                     type: PlacesUtils.bookmarks.TYPE_FOLDER,
+                                                     title: "a folder" });
+  let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: folder1.guid,
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 url: "http://example.com/",
+                                                 title: "" });
+
+  let manyFrencenciesPromise = promiseManyFrecenciesChanged();
+  await PlacesUtils.bookmarks.remove(folder1);
+  Assert.strictEqual((await PlacesUtils.bookmarks.fetch(folder1.guid)), null);
+  Assert.strictEqual((await PlacesUtils.bookmarks.fetch(bm1.guid)), null);
+
+  // We should get an onManyFrecenciesChanged notification with the removal of
+  // a folder with children.
   await manyFrencenciesPromise;
 });
 
+
 add_task(async function test_nested_contents_removed() {
   let folder1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
                                                      type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                      title: "a folder" });
   let folder2 = await PlacesUtils.bookmarks.insert({ parentGuid: folder1.guid,
                                                      type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                      title: "a folder" });
-  let sep = await PlacesUtils.bookmarks.insert({ parentGuid: folder2.guid,
-                                                 type: PlacesUtils.bookmarks.TYPE_SEPARATOR });
+  let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: folder2.guid,
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 url: "http://example.com/",
+                                                 title: "" });
+
+  let manyFrencenciesPromise = promiseManyFrecenciesChanged();
   await PlacesUtils.bookmarks.remove(folder1);
   Assert.strictEqual((await PlacesUtils.bookmarks.fetch(folder1.guid)), null);
   Assert.strictEqual((await PlacesUtils.bookmarks.fetch(folder2.guid)), null);
-  Assert.strictEqual((await PlacesUtils.bookmarks.fetch(sep.guid)), null);
+  Assert.strictEqual((await PlacesUtils.bookmarks.fetch(bm1.guid)), null);
+
+  // We should get an onManyFrecenciesChanged notification with the removal of
+  // a folder with children.
+  await manyFrencenciesPromise;
 });
 
 add_task(async function remove_folder_empty_title() {
   let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
                                                  type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                  title: "" });
   checkBookmarkObject(bm1);
 
@@ -243,12 +268,8 @@ add_task(async function test_nested_cont
                                                      type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                      title: "a folder" });
   await PlacesUtils.bookmarks.insert({ parentGuid: folder1.guid,
                                        type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                        title: "a folder" });
   await Assert.rejects(PlacesUtils.bookmarks.remove(folder1, {preventRemovalOfNonEmptyFolders: true}),
                        /Cannot remove a non-empty folder./);
 });
-
-function run_test() {
-  run_next_test();
-}