How do they have all their information? They have recording logs for every song he ever did, even ones that even they haven't heard.

People involved have a better idea than I do, but basically they draw information mostly from published interviews and research involving the people who were there--there's lots of it out there. Many of the sources are cited at the bottom of the page (the book The Vault is a major source for the general body of work) . If you look closely, you'll notice that the note "(assumed)" appears a whole lot in many of the entries--often the assumptions seem obvious, but that doesn't mean they're necessarily right (although many seem like pretty safe guesses).