From what I can tell from Reiko's Lunia database, you only have to kill Rigel 100 times in history but for Legend, you need to kill Rigel 100 times and then kill Soldin 100 times after that.
The final title isn't the only reward from this quest chain, by the way. One of the rewards is also a reward that "keeps on giving", so to speak (a new +1 skill point for EVERY time you rebirth!) Sigh, I wanted to do it when I saw the various rewards and the implications, but I lack the time for such things without delaying my next RB for an intolerable period of time.
Currently I'm main-ing two full-time fisher-girls. They fish. A lot.