Legal Question in Intellectual Property in California

Re: Intellectual Property

This DOES amount to a derivative work, but requires special permission from the rights holder. A Mechanical License does not cover what you propose.

Minor lyric changes (such as he/she changes to accomodate a singer of a different gender) are typically permitted by rights-holders, but wholesale changes to lyrics are NOT.

If it's a parody, making fun of the original, such as the kind of thing that Wierd Al Yankovic does, you may have some first-amendment right to do so, but otherwise, you'll need to negotiate directly with the music publisher for the song in question.