They're legal under the fair use policy, except if you use all of the song without modifying. This is why some AMV creators only use a portion of the song or combine parts of a song into one. If you use a full song in your AMV (sometimes even when you modified the audio) and post it onto Youtube and such, you might have to deal with copyright strikes, ads being injected into your video, or even getting your video taken down. This is only a risk though, because Youtube (in particular) is a huge pushover. You might not run into these problems at all, but they have happened before, especially with strict music labels like Warner MG, and other labels signed into it.
If you use something like a nightcore song or a remix, however, then I don't think you will run into problems with copyright. But I think it's safe enough to use a regular song and make sure to give credit. Be aware of the risks though.