This is the point, they would have evolved. Just cause they didn't have success doesn't mean they wouldn't have. You are watching Hall in the context of not playing with McD. So of course he appears to have different strengths. He is responding the situation he is currently being put in. You can't just say cause that is how he looks now that is how he would have looked with McD. He would have responded differently. You are trying to draw a conclusion about a situation from what you see now, not realizing that they would have adjusted differently and in ways you or I can't imagine. Hall would have focused more on puck retrieval ect if paired with Hall. Nuge is a prime example actually. Many said he should carry the puck and drive his own line. While a guy like Maroon or Lucic should play with McD and get the puck. Turns out Nuge is just fine not carrying the puck as much and focusing on retrieving it. It is really no different. Nuge didn't appear to be a good compliment for McD at all, turns out he was. It seems obvious now but that is just hindsight. It didn't appear obvious before it was actually tried.
So the point is who knows. Both are talented, smart, and fast players. There isn't a reason to think they couldn't have evolved to complement each other. We don't know, we sadly will never know.