"That he should have kept himself in training under the circumstances" is a noun phrase, the subject of "is remarkable".
"That" is a subordinator making the clause a noun phrase.
A less literary way of saying the same thing is:
"It is remarkable that he should have kept himself in training under the circumstances".
"Should", like most modals, has a range of meanings. The most common one is that of obligation (or duty, or the best chance of success), and that is what I think you are thinking of when you say "regret".
Here it does not have that meaning. It is a rather old fashioned usage, and in more modern writing would probably be "That he had kept himself in training under the circumstances". The used of "should have" (old-fashioned, as I say, but not completely obsolete) makes it more tentative: it is not saying that he did in fact kept himself in training and that was remarkable, but that even the possibility that he might keep himself in training is remarkable. (The surrounding text indicates that he did in fact keep himself in training, so this tentativeness is just a stylistic foible, but a common one in writing of that period).