--- a/browser/components/migration/AutoMigrate.jsm
+++ b/browser/components/migration/AutoMigrate.jsm
@@ -205,23 +205,43 @@ const AutoMigrate = {
     this._removeNotificationBars();
     histogram.add(10);
 
     let readPromise = OS.File.read(kUndoStateFullPath, {
       encoding: "utf-8",
       compression: "lz4",
     });
     let stateData = this._dejsonifyUndoState(yield readPromise);
-    yield this._removeUnchangedBookmarks(stateData.get("bookmarks"));
+    histogram.add(12);
+
+    this._errorMap = {bookmarks: 0, visits: 0, logins: 0};
+    let browserId = Preferences.get(kAutoMigrateBrowserPref, "unknown");
+    let reportErrorTelemetry = (type) => {
+      let histogramId = `FX_STARTUP_MIGRATION_UNDO_${type.toUpperCase()}_ERRORCOUNT`;
+      Services.telemetry.getKeyedHistogramById(histogramId).add(browserId, this._errorMap[type]);
+    };
+    yield this._removeUnchangedBookmarks(stateData.get("bookmarks")).catch(ex => {
+      Cu.reportError("Uncaught exception when removing unchanged bookmarks!");
+      Cu.reportError(ex);
+    });
+    reportErrorTelemetry("bookmarks");
     histogram.add(15);
 
-    yield this._removeSomeVisits(stateData.get("visits"));
+    yield this._removeSomeVisits(stateData.get("visits")).catch(ex => {
+      Cu.reportError("Uncaught exception when removing history visits!");
+      Cu.reportError(ex);
+    });
+    reportErrorTelemetry("visits");
     histogram.add(20);
 
-    yield this._removeUnchangedLogins(stateData.get("logins"));
+    yield this._removeUnchangedLogins(stateData.get("logins")).catch(ex => {
+      Cu.reportError("Uncaught exception when removing unchanged logins!");
+      Cu.reportError(ex);
+    });
+    reportErrorTelemetry("logins");
     histogram.add(25);
 
     // This is async, but no need to wait for it.
     NewTabUtils.links.populateCache(() => {
       NewTabUtils.allPages.update();
     }, true);
 
     this._purgeUndoState(this.UNDO_REMOVED_REASON_UNDO_USED);
@@ -414,26 +434,31 @@ const AutoMigrate = {
       return;
     }
 
     let guidToLMMap = new Map(bookmarks.map(b => [b.guid, b.lastModified]));
     let bookmarksFromDB = [];
     let bmPromises = Array.from(guidToLMMap.keys()).map(guid => {
       // Ignore bookmarks where the promise doesn't resolve (ie that are missing)
       // Also check that the bookmark fetch returns isn't null before adding it.
-      return PlacesUtils.bookmarks.fetch(guid).then(bm => bm && bookmarksFromDB.push(bm), () => {});
+      try {
+        return PlacesUtils.bookmarks.fetch(guid).then(bm => bm && bookmarksFromDB.push(bm), () => {});
+      } catch (ex) {
+        // Ignore immediate exceptions, too.
+      }
+      return Promise.resolve();
     });
     // We can't use the result of Promise.all because that would include nulls
     // for bookmarks that no longer exist (which we're catching above).
     yield Promise.all(bmPromises);
     let unchangedBookmarks = bookmarksFromDB.filter(bm => {
       return bm.lastModified.getTime() == guidToLMMap.get(bm.guid).getTime();
     });
 
-    // We need to remove items with no ancestors first, followed by their
+    // We need to remove items without children first, followed by their
     // parents, etc. In order to do this, find out how many ancestors each item
     // has that also appear in our list of things to remove, and sort the items
     // by those numbers. This ensures that children are always removed before
     // their parents.
     function determineAncestorCount(bm) {
       if (bm._ancestorCount) {
         return bm._ancestorCount;
       }
@@ -443,36 +468,42 @@ const AutoMigrate = {
         myCount = determineAncestorCount(parentBM) + 1;
       }
       bm._ancestorCount = myCount;
       return myCount;
     }
     unchangedBookmarks.forEach(determineAncestorCount);
     unchangedBookmarks.sort((a, b) => b._ancestorCount - a._ancestorCount);
     for (let {guid} of unchangedBookmarks) {
-      yield PlacesUtils.bookmarks.remove(guid, {preventRemovalOfNonEmptyFolders: true}).catch(err => {
+      // Can't just use a .catch() because Bookmarks.remove() can throw (rather
+      // than returning rejected promises).
+      try {
+        yield PlacesUtils.bookmarks.remove(guid, {preventRemovalOfNonEmptyFolders: true});
+      } catch (err) {
         if (err && err.message != "Cannot remove a non-empty folder.") {
+          this._errorMap.bookmarks++;
           Cu.reportError(err);
         }
-      });
+      }
     }
   }),
 
   _removeUnchangedLogins: Task.async(function* (logins) {
     for (let login of logins) {
       let foundLogins = LoginHelper.searchLoginsWithObject({guid: login.guid});
       if (foundLogins.length) {
         let foundLogin = foundLogins[0];
         foundLogin.QueryInterface(Ci.nsILoginMetaInfo);
         if (foundLogin.timePasswordChanged == login.timePasswordChanged) {
           try {
             Services.logins.removeLogin(foundLogin);
           } catch (ex) {
             Cu.reportError("Failed to remove a login for " + foundLogins.hostname);
             Cu.reportError(ex);
+            this._errorMap.logins++;
           }
         }
       }
     }
   }),
 
   _removeSomeVisits: Task.async(function* (visits) {
     for (let urlVisits of visits) {
@@ -485,20 +516,21 @@ const AutoMigrate = {
       let visitData = {
         url: urlObj,
         beginDate: PlacesUtils.toDate(urlVisits.first),
         endDate: PlacesUtils.toDate(urlVisits.last),
         limit: urlVisits.visitCount,
       };
       try {
         yield PlacesUtils.history.removeVisitsByFilter(visitData);
-      } catch(ex) {
+      } catch (ex) {
+        this._errorMap.visits++;
         try {
           visitData.url = visitData.url.href;
-        } catch (ex) {}
+        } catch (ignoredEx) {}
         Cu.reportError("Failed to remove a visit: " + JSON.stringify(visitData));
         Cu.reportError(ex);
       }
     }
   }),
 
   QueryInterface: XPCOMUtils.generateQI(
     [Ci.nsIObserver, Ci.nsINavBookmarkObserver, Ci.nsISupportsWeakReference]

--- a/browser/components/migration/tests/unit/test_automigration.js
+++ b/browser/components/migration/tests/unit/test_automigration.js
@@ -183,16 +183,17 @@ add_task(function* checkUndoPrecondition
   Assert.ok(true, "Should be able to finish an undo cycle.");
 });
 
 /**
  * Fake a migration and then try to undo it to verify all data gets removed.
  */
 add_task(function* checkUndoRemoval() {
   MigrationUtils.initializeUndoData();
+  Preferences.set("browser.migrate.automigrate.browser", "automationbrowser");
   // Insert a login and check that that worked.
   MigrationUtils.insertLoginWrapper({
     hostname: "www.mozilla.org",
     formSubmitURL: "http://www.mozilla.org",
     username: "user",
     password: "pass",
   });
   let storedLogins = Services.logins.findLogins({}, "www.mozilla.org",
@@ -252,16 +253,28 @@ add_task(function* checkUndoRemoval() {
   visits.root.containerOpen = false;
 
   yield AutoMigrate.saveUndoState();
 
   // Verify that we can undo, then undo:
   Assert.ok(AutoMigrate.canUndo(), "Should be possible to undo migration");
   yield AutoMigrate.undo();
 
+  let histograms = [
+    "FX_STARTUP_MIGRATION_UNDO_BOOKMARKS_ERRORCOUNT",
+    "FX_STARTUP_MIGRATION_UNDO_LOGINS_ERRORCOUNT",
+    "FX_STARTUP_MIGRATION_UNDO_VISITS_ERRORCOUNT",
+  ];
+  for (let histogramId of histograms) {
+    let keyedHistogram = Services.telemetry.getKeyedHistogramById(histogramId);
+    let histogramData = keyedHistogram.snapshot().automationbrowser;
+    Assert.equal(histogramData.sum, 0, `Should have reported 0 errors to ${histogramId}.`);
+    Assert.greaterOrEqual(histogramData.counts[0], 1, `Should have reported value of 0 one time to ${histogramId}.`);
+  }
+
   // Check that the undo removed the history visits:
   visits = PlacesUtils.history.executeQuery(query, opts);
   visits.root.containerOpen = true;
   Assert.equal(visits.root.childCount, 0, "Should have no more visits");
   visits.root.containerOpen = false;
 
   // Check that the undo removed the bookmarks:
   bookmark = yield PlacesUtils.bookmarks.fetch({url: "http://www.example.org/"});
@@ -607,11 +620,32 @@ add_task(function* checkUndoVisitsState(
   Assert.equal(yield visitsForURL("http://www.example.org/"), 2,
                "2 example.org visits should have persisted (out of 4).");
   Assert.equal(yield visitsForURL("http://www.unrelated.org/"), 1,
                "1 unrelated.org visits should have persisted as it's not involved in the import.");
   yield PlacesTestUtils.clearHistory();
 });
 
 add_task(function* checkHistoryRemovalCompletion() {
+  AutoMigrate._errorMap = {bookmarks: 0, visits: 0, logins: 0};
   yield AutoMigrate._removeSomeVisits([{url: "http://www.example.com/", limit: -1}]);
   ok(true, "Removing visits should complete even if removing some visits failed.");
+  Assert.equal(AutoMigrate._errorMap.visits, 1, "Should have logged the error for visits.");
+
+  // Unfortunately there's not a reliable way to make removing bookmarks be
+  // unhappy unless the DB is messed up (e.g. contains children but has
+  // parents removed already).
+  yield AutoMigrate._removeUnchangedBookmarks([
+    {guid: PlacesUtils.bookmarks, lastModified: new Date(0), parentGuid: 0},
+    {guid: "gobbledygook", lastModified: new Date(0), parentGuid: 0},
+  ]);
+  ok(true, "Removing bookmarks should complete even if some items are gone or bogus.");
+  Assert.equal(AutoMigrate._errorMap.bookmarks, 0,
+               "Should have ignored removing non-existing (or builtin) bookmark.");
+
+
+  yield AutoMigrate._removeUnchangedLogins([
+    {guid: "gobbledygook", timePasswordChanged: new Date(0)},
+  ]);
+  ok(true, "Removing logins should complete even if logins don't exist.");
+  Assert.equal(AutoMigrate._errorMap.logins, 0,
+               "Should have ignored removing non-existing logins.");
 });

--- a/toolkit/components/telemetry/Histograms.json
+++ b/toolkit/components/telemetry/Histograms.json
@@ -5168,16 +5168,49 @@
     "bug_numbers": [1309617],
     "alert_emails": ["gijs@mozilla.com"],
     "expires_in_version": "57",
     "kind": "enumerated",
     "n_values": 5,
     "releaseChannelCollection": "opt-out",
     "description": "Indicates we showed a 'would you like to undo this automatic migration?' notification bar. The bucket indicates which nth day we're on (1st/2nd/3rd, by default - 0 would be indicative the pref didn't get set which shouldn't happen). After 3 days on which the notification gets shown, it will get disabled and never shown again."
   },
+  "FX_STARTUP_MIGRATION_UNDO_BOOKMARKS_ERRORCOUNT": {
+    "bug_numbers": [1333233],
+    "alert_emails": ["gijs@mozilla.com"],
+    "expires_in_version": "58",
+    "keyed": true,
+    "kind": "exponential",
+    "n_buckets": 20,
+    "high": 100,
+    "releaseChannelCollection": "opt-out",
+    "description": "Indicates how many errors we find when trying to 'undo' bookmarks import. Keys are internal ids of browsers we import from, e.g. 'chrome' or 'ie', etc."
+  },
+  "FX_STARTUP_MIGRATION_UNDO_LOGINS_ERRORCOUNT": {
+    "bug_numbers": [1333233],
+    "alert_emails": ["gijs@mozilla.com"],
+    "expires_in_version": "58",
+    "keyed": true,
+    "kind": "exponential",
+    "n_buckets": 20,
+    "high": 100,
+    "releaseChannelCollection": "opt-out",
+    "description": "Indicates how many errors we find when trying to 'undo' login (password) import. Keys are internal ids of browsers we import from, e.g. 'chrome' or 'ie', etc."
+  },
+  "FX_STARTUP_MIGRATION_UNDO_VISITS_ERRORCOUNT": {
+    "bug_numbers": [1333233],
+    "alert_emails": ["gijs@mozilla.com"],
+    "expires_in_version": "58",
+    "keyed": true,
+    "kind": "exponential",
+    "n_buckets": 20,
+    "high": 100,
+    "releaseChannelCollection": "opt-out",
+    "description": "Indicates how many errors we find when trying to 'undo' history import. Keys are internal ids of browsers we import from, e.g. 'chrome' or 'ie', etc."
+  },
   "FX_STARTUP_MIGRATION_DATA_RECENCY": {
     "bug_numbers": [1276694],
     "alert_emails": ["gijs@mozilla.com"],
     "expires_in_version": "57",
     "keyed": true,
     "kind": "exponential",
     "n_buckets": 50,
     "high": 8760,