Given Malady was looking to talk to the Advocate on Bloodmoon Isle, guessing at a pact with a powerful demon seems quite believable.