I am not a copyright expert, but I do own a few of Weird Al albums and he is very diligent about obtaining permissions from artists he is covering.
IIUC, Weird Al probably doesn't need permission for his parodies, legally speaking. He does get it anyway.
It’s not a copyright issue, it’s a right of publicity issue, a completely separate legal issue (conceptually, more trademark-like than copyright-like, but distinct from either.)