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.
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.)