It's not clear to me if remixes by definition are based on recorded samples, but it doesn't really matter except that anything based on a recording would also involve an additional layer of permission. You've created a derivative work. In the US, 17 USC 106 (2) tells you that the copyright owner has the exclusive right to authorize derivative works, so you're right, there are consequences. You would need to obtain permission for that derivative work. There is a concept of a compulsory license, which should not distract you (it does not apply to significantly reworked works as you have created). So first and foremost, permission is necessary, and that would take the form of some kind of license (if permission is granted). It isn't just an issue of paying a fee.
[EDIT]
I want to clarify that reliance on terms like "cover song" and "remix" in certain websites (esp. those that provide "compulsory licensing" services) can lead one down the wrong path. The Gov copyright office provides a guide for compulsory licensing which is the path for copying that involves "just paying a fee", and it notes that the work "shall not change the basic melody or fundamental character of the work", and "the primary purpose in making the phonorecords is to distribute them to the public for private use. It is not available for phonorecords intended for use in background music systems, jukeboxes, broadcasting, or any other public use".
There are numerous services that allow you to sign up for quick and easy licensing of "covers", so if you conclude that your work is a "cover", you might think that these services are just what you're looking for. Copyright law is not defined in terms of the concept "cover". So be cautious in interpreting what you read. If they direct you to case law that supports the idea that you can publicly perform what you have derivatively created, then (a) you'd be on firmer grounds, (b) you should consult an attorney and (c) I'll eat my hat. Basically, any performance is copying, as every business that sang "Happy Birthday" knew for nearly a century.
