Context: US based answer. I’m a professor and former department chair who has had a lot of experience with situations like these, both on the hiring side and in other ways.
When is the best time to mention this two body problem?
It’s important to understand (and this is something that I think the other answers are missing) that this question has no right answer. There isn’t a “best time”, just different pros and cons to mentioning it at different times.
If he mentions it early in the interview process, he is giving information that is potentially useful to the interviewing department. They may be able to help with the two-body problem, which would give them a competitive edge over other departments. This could make them more excited about the prospect of hiring him, and a bit more likely to make him an offer. They could also tell him and you about resources that may be available to help with situations like these, like extra funding to support your acceptance to the local PhD program, which could help you focus your own search efforts and perhaps ease some of the stress you may be dealing with.
Alternatively, the information may make the department less excited, and a bit less likely to choose to make him an offer, if they get a sense that the hurdle of causing him to choose to move to their city is improbably difficult or too much trouble. This could happen for example if your area of PhD specialization is so esoteric that they think it is very unlikely that you’ll be able to find a co-supervisor in their university or another nearby one, or if your partner is only a marginally attractive candidate to them to begin with.
At the very least, revealing this kind of information early on will signal that your partner is a serious person with a professional attitude, who is engaging with the interview process in good faith and is not wasting people’s time by playing games. Some people (me, for example) would be impressed by such an attitude, and that could also conceivably affect the likelihood of getting an offer. Even if he doesn’t get an offer, it’s always good to leave a good impression as this could end up helping in various ways with his future career.
Conversely, springing this information on the department at a late stage after an offer has been extended may (or may not, depending to some extent on the local culture and on the way he brings this information up) feel like he is pulling a bit of a “bait and switch” maneuver on them. It may be a dealbreaker and leave the interviewers with a sense that their time has been wasted, leaving a sour aftertaste.
Finally, revealing the information early on may help avoid wasting his (and your own) time and mental energy. Bringing this up could give both of you useful information and possibly rule out that institution as a viable option. If there is no hope for you to find a PhD co-adviser where he is interviewing, are you both sure that there is a point in going through the interview process?
What is a good way of phrasing it?
In a forthright and polite way. He should simply explain the situation and avoid giving any obvious signs of dishonesty or immaturity by disclosing misleading information or answering follow-up questions evasively.
Is it possible that mentioning the two body problem will reduce his chances of getting the position?
Yes. It’s also possible that it will increase the chances as I explained above. The most likely effect will be that the chances of him getting hired will not really be changed at all, but the interview process will go more smoothly and pleasantly for both your partner and the people interviewing him, he will leave a slightly better personal impression, and you and him will be a little bit less stressed out while the process is playing out.
Summary. At my (US) university it is definitely helpful to mention a two body problem early on. We have lots of experience and resources to support candidates and their family members in those situations, and usually see them as an opportunity rather than a reason for discouragement or to give up on promising candidates. During the years when I was a department chair I interviewed around 20-30 tenure track candidates, and the topic was a standard one to discuss, and one that we were able to help with on several occasions leading to a successful recruitment.
On the other hand, the other answers suggesting not to mention it until late in the process also have a valid point. I don’t think anyone will argue that your partner has an ethical obligation to explain his personal circumstances before receiving an offer, and if he feels that there is a strategic advantage to withholding this type of information, it’s perfectly legitimate to do so, and there are specific situations where that could be a good idea. However, personally I think any perceived advantage to such an approach may not be as significant as people without experience in such matters typically think, and may be nonexistent.