* Sistani's call could hasten Maliki departure
* Political deadlock hurts fight against Islamic State
* Islamic State warns women to wear full veils, destroys shrines (Adds Islamic State's destruction of two shrines in Mosul, edits throughout)
By Raheem Salman and Isra' al-Rubei'i
BAGHDAD, July 25 (Reuters) - Iraq's most influential Shi'ite cleric urged political leaders on Friday to refrain from clinging to their posts - an apparent reference to Prime Minister Nuri al-Maliki, who has defied demands that he step aside.
Speaking through an aide who delivered a sermon after Friday prayers in the holy city of Kerbala, Grand Ayatollah Ali al-Sistani said leaders should show flexibility so that political deadlocks could be broken and Iraq could confront an insurgency.
Maliki has come under mounting pressure since Sunni militants led by the hardline Islamic State swept across northern Iraq last month and seized vast swathes of territory, posing the biggest challenge to Maliki's Shi'ite-led government since U.S. forces withdrew in 2011.
Critics say Maliki is a divisive figure whose alienation of Sunnis has fuelled sectarian hatred and played into the hands of the insurgents, who have reached to within 70 km (45 miles) of the capital Baghdad.
Sistani said it is time for politicians to think of Iraq's interests, not their own.
"The sensitivity of this phase necessitates that all the parties concerned should have a spirit of national responsibility that requires the practice of the principle of sacrifice and self-denial and not to cling to positions and posts."
Maliki, a Shi'ite, has ruled since an election in April in a caretaker capacity, dismissing demands from the Sunnis and Kurds that he step aside for a less polarising figure. Even some Shi'ites oppose his bid for a third term.
Despite pressure from the United States, the United Nations, Iran and Iraq's own Shi'ite clergy, politicians have been unable to quickly come up with an inclusive government to hold the fragmenting country together.
Iraq's parliament took a step toward forming a new government on Thursday, when lawmakers elected senior Kurdish lawmaker Fouad Masoum as president.
The next step, choosing a prime minister, may prove far more difficult as Maliki has shown no sign he will give up his post.
Sistani's call for flexibility could hasten his departure. He is seen as a voice of reason in the deeply divided country, and has almost mythological stature to millions of followers, members of Iraq's Shi'ite majority.
The 83-year-old cleric who hardly ever appears in public last month seized his most active role in politics in decades by
calling on Iraqis to take up arms against the Sunni insurgency.
The insurgents, who hold territory in Iraq and Syria and have declared a 'caliphate', aim to redraw the map of the Middle East and have put Iraq's survival as a unified state in jeopardy. The army virtually collapsed in the face of their lightning advance.
Shi'ite militias and Kurdish peshmerga fighters have become a critical line of defence against Islamic State as the militants set their sights on the capital.
U.S. military and Iraqi security officials estimate the Islamic State has at least 3,000 fighters in Iraq, rising towards 20,000 when new recruits since last month's advance are included.
ISLAMIC STATE RULES
Aside from military campaigns, Islamic State has also been purging the plains of northern Iraq of religious and ethnic minorities that have co-existed there for hundreds of years.
Insurgents have also been stamping out any influences they deem non-Islamic in Mosul, a once diverse city of two million that fell to the militants on June 10.
Eyewitnesses said Islamic State gunmen destroyed the tombs of two prophets on Friday. The destruction of the Jirjees and Sheet shrines came a day after militants blew up the Nabi Younes shrine, one of the city's most well-known and thought to be the burial site of a prophet referred to in the Koran as Younes and in the Bible as Jonah.
Also on Friday, the group warned women in Mosul to wear full-face veils or risk severe punishment.
"The conditions imposed on her clothes and grooming were only to end the pretext of debauchery resulting from grooming and overdressing," Islamic State said in a statement.
"This is not a restriction on her freedom but to prevent her from falling into humiliation and vulgarity or to be a theatre for the eyes of those who are looking."
A cleric in Mosul told Reuters that Islamic State gunmen had shown up at his mosque and ordered him to read their warning on loudspeakers when worshippers gather.
"Anyone who is not committed to this duty and is motivated by glamour will be subject to accountability and severe punishment to protect society from harm and to maintain the necessities of religion and protect it from debauchery," Islamic State said. (Additional reporting by Maggie Fick; Writing by Michael Georgy; Editing by Angus MacSwan and Susan Fenton)