The mechanical license you purchased for recording and distributing the songs (as MP3s or on vinyl or CDs) differs from the license needed for using your version of the song in a video (referred to as a "sync license"). Sync licenses are negotiated directly with the copyright holder. Unfortunately, no collective like HFA provides blanket sync licensing (although various sites may negotiate sync licenses for a fee).
Typically, you're on the defensive with YouTube. Even if you acquire the proper licenses, an initial objection may be prompted by Content ID or the Copyright Match Tool. At that point, you'll need to provide evidence of your license, or in the case of a takedown, a DMCA counter-notice. (A song owner can block, track or monetize an infringing video.) Even though covers may be harder to detect (because they don't match the digital fingerprint of the original version), there are methods for locating them, for example, text searching software that detects titles or lyrics. In some cases, YouTube can facilitate a revenue-sharing arrangement with the song owner. Bottom line: Because most song infringements on YouTube are monetized, not taken down, you may want to forego the sync license and wait and see if a copyright claim is made against your video.