The oldest DNA from Africa is 15000 years old. From Europe it's 120,000 years, and from Siberia they have horse and mammoth DNA from molars that are [700,000 to 1,2 milliom years old][1]. It's feasible that they will find homo erectus and habilis DNA from cold regions.
The more bone and tooth fragments the better. Then a comparative anatomist can study the age and differences of the bone fragments and articulations to see if they have a lot of similarity with a currently known homo species.
If they can find enough differences in bones of a specimen, concensus can agree that it's a new species. It takes quite a lot of bone to decide that. a small shard isn't enough. Half a skull/leg is fairly vague evidence and half a skeleton can be generally convincing. [1]: https://www.science.org/content/article/mammoth-molars-yield-oldest-dna-ever-sequenced#:~:text=1.2%2Dmillion%2Dyear%2Dold,record%2C%20reveals%20new%20mammoth%20lineage&text=A%20genetic%20analysis%20of%20long,the%20oldest%20DNA%20yet%20sequenced.