I don’t know what you should do if your results vary. For me this took 4 minutes and ended with a green check mark that everything was fine.
Select your primary disk (usually Macintosh HD) and click on First Aid. It looked to me like the same Disk Utility you could get at without Repair Mode but you have to be in Repair Mode. Once in Repair mode, you will be shown a list of 4 choices.
Get into Repair mode by powering down your Mac, then immediately after pressing the Power button to turn it back on, press and hold Command-r (⌘+r) for a while, until the Mac does NOT show a booting scroll bar, but instead asks you a question or two like “Language?” Note you must power down, not just Restart, since you can’t do Command-r fast enough during a Restart. Steps Apple Support took me through to fix this: My setup: A new (2019) MacBook Pro 15' running Mac OS Mohave (10.14.5) with a new 4TB WD My Passport. I had my first complete backup yesterday, and about 20 successful hourly backups since then. It took 3 calls to Apple Support, but they have solved it for me. I had exactly the same problem - no matter how many times a I rebooted my Mac or reformatted my WD drive, the first Time Machine backup would succeed and any subsequent one would fail with “Error occurred while creating the backup folder”.
