I just had the hard drive replaced in my Dell XPS15 because of a vibration problem. It now does something similar.
Here is some background: I think this part is reliable information. When the computer boots with a brand new device, it is supposed to go through the "checking media" thing. In addition, the tech said that the first "checking media" message always says "[fail]" - always, in his experience; it apparently has something to do with scanning for USB drives and not finding any, something like that. That first "[fail]" does not indicate a problem.
When I got my computer new, it never did the "checking media" thing, and booted in a second or two. Since the HD was replaced, however, it always does the "checking media" thing, and takes a long time to boot, like yours.
Now my supposition. The problem here is not that the "checking media" says "[fail]"; rather, the problem is that it should not be doing the "checking media" thing at all. I suspect that the media is supposed to be marked as "clean" after a successful boot, or during a clean shutdown, something like that. But this is not happening, hence the media checks on every restart. This theory is supported by the fact that when I restart my computer, now, Windows always tells me that it experienced a serious error and didn't shut down cleanly, even when I just did a clean shutdown with no errors. So the message you quote is not a problem, it's a consequence of a problem that occurred during ?shutdown? or before.
UPDATE: after a service call with Dell, the problem is at least partially resolved. It appears the supposition was roughly correct. The Dell tech directed me to fix the boot order. I know, it sounds unlikely. But apparently having the boot order wrong was preventing the new drive from ever getting marked as "clean", and hence the "checking media" sequence every time it was powered on. The issue is that this is a new UEFI BIOS machine and changing the boot order was a maze of twisty passages made worse by the fact that the Dell tech didn't really know how to do it either. I can recall that I had to enable Legacy boot mode, change the boot order there, disable Legacy boot mode and reenable UEFI boot mode so that Windows would boot. I will have another look and add another update if I can figure out how to be more specific.
Now the checking media stuff is gone but this morning, it still took a long time in the BIOS and when it came up I got the "Your PC ran into a problem" message from Windows, indicating a likely driver issue in Windows during shutdown. This again is probably a consequence of unpacking an inconsistent/outdated Windows from the replacement HD and if you are using Ubuntu, it may not be relevant to you.