If a person is Jewish by maternal decent, but can't prove it conclusively through documents. Do they need to convert? Do they need normal conversion or giyur l'chumra? What are the steps involved? I read about giyur lechumra, but heard that it can only be done back four generations. Is that true?
I don't believe any recognized Beit Din will do giyur, or giyur l'chumra to someone who is otherwise validly Jewish. Typically a Beit Din, if there is a possibility that you are legitimately Jewish, will require that you hire a genealogist. I worked for a while with Vaad HaRabbonim Haolami LeInyonei Giyur under Rav Eliahshiv and have been a part of several cases with the Israeli Rabbinut(as an askan for Rav Ovadia Yosef) and that was the standard procedure. Most commonly it was applied to Sem girls who wanted to marry in Israel and needed definitive genealogical proof of Judaism.
Almost every nation has birth, death and burial records going back hundreds of years. All you would need is to connect the dots, matrilineally to someome buried in a Jewish graveyard(at a minimum). In a case that I was a part of in Philadelphia twelve years ago with Rav Dov Brisman, we had a girl with a genealogists report that gave her matrilineal decent back 7 generations, and that sufficed.
As far as Giyur L'Chumra, how recent(or not) the suspected claim of Judaism is that a Beit Din will want is entirely up to the Beit Din. There is no halakha for it. According to the Shulhan Arukh Y"D 269(and thus the way of the Israeli Rabbinate) a Giyur L'Chumra is only done when there is a prior conversion by an unknown/unrecognized Beit Din, and then only under very specific circumstances. I know that the Israeli Rabbinut has broadened(and at times restricted) that definition over the years. For an understanding of that one would need to look in the various Teshuvot in the Yaskil Avdei starting with volume 4(that is when the Rav became the first president of Beit Din HaGadol), and the various volumes of Piskei Din.