Weird Al has to pay for the right to use the SCORE (music without lyrics) when he makes his music. He uses part of the original and adds his own thing.
Pardody in the film world is different. You won't be using any of the original material, you will be making fun of it. You will take a situation and treat it differently. AFAIK, parody is covered legally and you don't need the rights. If you used any of the music, actors voices, or any imagry, then you have rights issues. But parody is fine.
Many a court case has been thrown out because the the parody clause.