He’ll want to show travel together as much as possible. If he saved any receipts of airline tickets (emails sent by airline), hotel and the like, that is useful. It sounds like this has gone on for years so he may have to work with what all he can get his hands on along with the passport stamps.
Pictures together-especially together with family and in social settings. Label and date them. Cover a span of time. You don’t need hundreds, but a couple per year.
Printout snippets of chats together. The content isn’t important as much as a regular communication. Emails to each other.
Any document at all that was given to them as husband and wife. Invitations or anything. Email printouts as well.
Records of money remittances.
If he made her an authorized user on a debit/credit card, record of that.
Any other bank or credit card records showing he spent money in her town.
Anything else, no matter how random that has their names on it together can help.