I am not a lawyer. This is not legal advice. If you in anyway construe it as such you are incorrect in doing so.
If you want to obtain a license I would do the research and try to contact the publisher directly. If that doesn't work could move on to Harry Fox.
I worked as a music supervisor on a couple of feature films for a nanosecond about 15 years ago. Okay, it was more like three years of hell dealing with copyright and licensing when all I wanted to be doing was contracting musicians and spending time at the studio producing the recordings for the soundtracks. Instead, I spent an inordinate amount of time at the production office on the phone with publishing companies. One non-musical task I did enjoy, however, was researching folk songs at the Library of Congress for one particular film. Then it came time to inform the producers and director that most of the music they insisted was in the public domain was not. I learned a lot about copyrights and how to give tens of thousands of dollars of bad news to people that are especially averse to bad news and like being wrong even less. They were, for the record, very nice about it.
So, there's my background, take what follows for what it's worth. Did I mention this is in no way any form of legal advice?
To record another artists song, as you have done, technically requires you to acquire proper permissions from the owners of the copyrighted material you are recording. Technically, the act of recording another person's copyrighted song, whether you plan to distribute it or not (posting online is a form of distribution), for profit or not, requires permission from the owner of the copyright which is usually the publisher. Uploading said recording of copyrighted material to a website on the internet is a form of distribution. Bear in mind, also, that not every copyrighted song is necessarily one that has been "published". That situation creates it's own issues. If uploaded to a website that is "for profit" there are even bigger issues that can come into play. The "fair use" argument has often been used successfully and probably failed just as often. I won't speculate as to why any number of people do or do not get in trouble for uploading cover songs because I don't have a clue and it surprises me more than it does you.
That wasn't as short as I would have liked to so I'll cut to the chase:
Recording another artist's copyrighted work without obtaining the "right" to "copy" the artist's work is illegal.
Now the good news (sort of):
http://suebasko.blogspot.com/2011/06/cover-songs-on-youtube.html
EDIT:
I forgot to add that uploading a video of a cover song also requires a "sync" license.