The Naka Shrine had been in the Uchiha's possession for generations and was brought with them when they settled in Konoha. Through careful study, Madara was able decipher enough of it to learn of the history of shinobi: of the endless cycle of failed peace and the destiny of battle between Uchiha and Senju, but also a means of unity for the world. With this knowledge, Madara decided Konoha was a failed experiment. He tried to convince his own clan and even Hashirama of the same conclusion, but none would hear him. Madara chose to abandon the village, returning with the Nine-Tailed Demon Fox under his control to challenge Hashirama. They fought to exhaustion, and from the carnage of their battle the Valley of the End was formed. In the end, Madara, too tired to even keep his Sharingan activated, was killed by Hashirama.
So after he abandoned his clan and his people and then got killed by Hashirama, how was the next clan leader chosen? (I believe Madara wasn't married)
Right before Madara left his own clan, Konoha was founded as a place where Uchiha and Senju could co-exist peacefully.
After Madara's death, there was no true leader for the Uchiha clan. All of them were under one leadership of Hokage along with rest of the citizens of Konoha. Hashirama was elected as the first Hokage and he was later succeeded by Tobirama.