First, the fact that Snape provided information which proved to be legit about his master's intent to kill the Potters. Snape betrayed Voldemort - who was then at the height of his power - to trying to save Lily. That alone tells enough about Snape's priorities.
His remorse story was also plausible, considering Severus's friendship with Lily till their 5th year. What kind of bigoted blood supermacist has a muggleborn for best friend for years? A conflicted one, who puts his feelings above his ideology.
Then, after Lily's death, Dumbledore witnesses him falling to pieces. That's a pretty dramatic performance for an usually reticent guy, but sure, it might have been just that, a show to gain Dumbledore's trust. Unlikely, but it was possible. But later Snape proved his words with actions: In Harry's first year Snape protects him and does everything to assist Dumbledore to get rid of his former master. And continues to do so all the following years.
Snape never gave Dumbledore any reason to doubt his motivations, and was very useful and competent. It seems from their dialogues in DH, The Prince's Tale that they had a good 'work relationship' and cautious and secretive Dumbledore, who usually played with his cards close to the chest, and was reluctant to give more than the the essential information, speakingpreferring to speak in riddles and giving mere hints, did trust Snape, his conclusions based on observations for years he knew Snape, and so he was fairly open with him.