Hadji is derived from the Arabic Hajj, used to denote the pilgramage to Mecca. Muslims would the add the Hadji element to their names after they had completed the pilgramage.
During Ottoman times, the Greeks began to also use it to denote the Christian pilgrimage to Jerusalem, which was very important at the time. The name survives now as an appengae to other names such as Theodoulou, which again is a Greek Christian name meaning Servant of God.
If your relative was Macedonian, then he/she was a Greek Macedonian, ie a real Macedonian, not a Slav Macedonians from the Former Republic of Macedonia. They have Bulgarian names which end in 'ski or 'ev. HadjiTheodoulou is an exclusively Greek name.