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