More information of degraded dna handling techniques, albeit in the forensics field and aimed toward people, but interesting to me nonetheless 
 - http://www.nature.com/nature/journal/v432/n7018/full/nature0...
 - http://epublications.bond.edu.au/cgi/viewcontent.cgi?article...
I don't know how it relates to million years old samples though. Maybe someone else knows why that's not easily applicable. I'd guess degradation being pretty random leaves chunks which are too small for analysis. (pure speculation, please educate me)
Edit: Wow a lot of bs going on in the comments. First of all, there's an immense number of ways a DNA strand can degrade, and only one of them splits the strand in two. The relative importance of all these pathways depend on the environment of the DNA, which obviously changes for each and every fossil you have. The global kinetics of "DNA degradation" are supposedly first-order, which implies constant half-life.
And I guess it might for every cell of a single fossil.
No, the only way for something to survive is if the half life model breaks down and the chance of decay during different time periods isn't independent. This would be the case if one of the strands was somehow preserved accidentally.
That half-life is the time it takes for the link between half of the bonds between nucleotides to break (http://www.nature.com/news/dna-has-a-521-year-half-life-1.11...)
So, after 1042 years, only a quarter of the bonds will be intact. After 100 million years, only 1 in every 2^190000 bonds will be expected to still be intact. Taking 2^10 = 1000, that's 1 in every 10^57000. I think that's quite a bit higher than our estimate for the number of particles in the universe (https://www.quora.com/How-many-particles-are-there-in-the-un...)
TL/DR: I wouldn't bet on it.
 - http://www.calculator.net/half-life-calculator.html?type=1&n...