Here are some Google search results. I found it surprising that the first form is the most common (I'd have thought the second):
"What is that to do with" -> About 323,000,000 results.
"What does that have to do with" -> About 28,000,000 results.
"What has that got to do with" -> About 2,700,000 results.
"What has that to do with" -> About 1,530,000 results.
