The Earthlings will continue to use the Gregorian calendar (even other civilizations besides Western use it for buisness and trade purposes) and look a their digital watches for correct dates and years. Locally they may adjust their schedule to Martian days (NASA called them sols back during Viking, I will too). Since its only been 20 years (10 martian years lets call them annus sg. annus 4th declension) most of the Earthlings are still going to be tied to time/dates on Earth and record all information as such. We do it here, just becasue your writing about Islam and the middle east you dont use the Moslem lunar calendar you use the Gregorian one. Future Earth travelers would do the same.
The native Martians should have developed thier own calendar systems related to what they observe. A 668 sol annus (668.5921 Martian days in a Martian year) the number of times it takes Mars to rotate in a revolution about the Sun. Now they need to break it up. Since they don't have a good large moon months don't make sense. Demios only takes 30hrs, and Phobos 7.6hrs to rotate around mars to not good for long term time keeping. Astronomically they can observe equinoxes and solstices so use them first. I had to look this data up:
Spring lasts 193.30 sols
Summer lasts 178.64 sols
Autumn lasts 142.70 sols
Winter lasts 153.94 sols
No thats doesnt add up exactly to 668.5921 sols. Worry about that later just like our ancestors did. That gives us 4 "holidays". Round off the numbers for when they occur. Spring Equinox sol 1, Summer Solstice sol 193, Autumnal equinox sol 372, Winter solstice sol 515, Spring again sol 669 or 1 new annus. This gives them 4 periods to use like we do months. They are a bit long so maybe they divide them up more later.
668 divided by eight gives us 83 weeks with 4 days left over. Make the week 8 sols long and make the 4 holidays extra-weekly. The auunus then starts on the same named sol everytime. Want sol names? Name them the same some of our ancient civs did after the "planets": Sun, Demios, Phobos, Mercury, Venus, Earth, Jupiter, Saturn. Nice of Mars to have 2 moons for this.
Now that there are 8 sol weeks use them to divide up the periods better. Lets make each "month" (ok I need a new word back to my latin: mensis) 32 sols. So the first period has 6 32 sol mensis with 1 day left over add it to the last mensis. The second period has 5 mensis with 19 sols left over, enough for another mensis. The 3rd 4 mensis with a short mensis of 15 sols. And the 4th 4 mensis with a short mensis of 26 sols. A total of 18 "correct" mensis, 3 shorter and 1 longer, 22 mensis to compare with our 23.5 over the same time. I did the math wrong and all that ads up to 669 sols but you get the idea.
Now you have the problem of the annus not exacly corresponding to the solar year and need leap years since its close to half an extra sol an annus lets do a leap annus every annus instead of every 4 years. since I already introduced intercalendary days do the same with this one, it doesnt belong to a month or a day of the week just tack it on the end of the year. The calendar is still going to get off rather quickly but its easy to fix. The preists/astronomers just add intercalendary days before the vernal equinox whenever they notice the cycle getting off, a lot of annus would end of with 669 or 670 sols.
Sol Mensis 1 Spring Equinox None 1-32 Mensis 1