AHD traces sahib through the Hindi* from the Arabic; -istan, from an Iranian root meaning to stand, does mean country. It doesn't say anything about -abad, but city sounds good, all things considered.

*Hindi and Urdu are closely related.