Construct takes an object, and gerunds can take objects. The monument is an object of constructing.
Their constructing the monument was something of a feat
You can use of X to explicitly provide the reason, purpose, or "destination" of many nouns. The monument is the "destination" or reason for the constructing. As gerunds are nouns this can be done with them as well.
Their constructing of the monument was something of a feat.
Both expressions are basically two paths that arrive at the same meaning.
If you wished to draw attention to the monument - i.e. if the act of constructing the monument is a feat and not just the act of constructing (without regard to what is being constructed) - then the second sentence would be better.