Edit: I have updated my answer with improved analysis. My old answer was flawed in its analysis
The question of population survival depends on enough genetic material being preserved to maintain a healthy population. The first thing is that there will only be at most 5 Y-Chromosomes in the world after the disaster, and some places may have only one for quite some time (for example if one of the men is in Australia or New Zealand his descendents might be very isolated). However provided that Y-Chromosome is generally healthy that won't be a major problem - it will create higher vulnerability in men to particular illnesses but that's not enough to guarantee the population will go extinct especially as the Y-Chromosome will be paired with different X-Chromosomes in different men.
Now it worth looking at breeding strategies and I'll consider a bit of a worst case scenario where a man can only produce 100 children before dying of "over-exertion" (this is only for simplification of the analysis). So the man successfully produces 100 healthy offspring (that is children who reach reproductive age) before dying. He should focus on mating with older women who are still fertile (i.e. those in their 30's) as this will be their very last chance to pass on genetic material.
First generation
This generation of 100 children will all be half-siblings, having half their genetic material from the proto-man. If these half-siblings were to breed with each other it would be a problematic level of in-breeding and applicable to incest laws, but there is no need for this as after approximately 13 years the ~50 sons will reach reproductive age and at this point women who were 20 years old will still be fertile and the sons should focus on mating with those women and not mate with their half-sisters or other girls their own age. Let's say that all of them also produce 100 offspring before dying of over-exertion.
Second generation
This generation of 50,000 children all have a common grandfather so 25% of their DNA comes from the original man while the other 75% comes from random women. This is already a much improved level of genetic diversity and some countries incest laws would not prohibit pairings between individuals with this level of genetic similarity, although it's still somewhat less than ideal.
After ~26 years the grandsons will reach 13 years old, they should mate with the women who were infants at the time of the dieoff, these women will now be ~26 years old. Once again let's assume each grandson produces 100 succesful offspring before dying of over-exertion.
Third generation
This generation of 2,500,000 children (yes, 2.5 million, the wonders of exponential growth!) all have a common great-grand-father and so 12.5% of their genetic material comes from the original man, and the other 87.5% comes from random women. At this level of genetic similarity incest laws are not applicable anymore and inbreeding will generally not be problematic. This is the first generation where unmated "original" women might realistically run out - that's not a problem though as each woman can bear multiple offspring.
Fourth Generation
It may even be possible to get one final generation with unrelated women. The fourth generation will come of age at a time when the girls who were babies at the time of the great dieoff are 40 years old, and girls made from frozen embryos/sperm would be a bit younger, at least some of these women should still be fertile. This fourth generation would have a great-great-grandfather in common and only 6.25% of their genetic material would come from the original man.
Overall if the women successful hold society together and utilize such a breeding strategy then even with only a single man who dies quite quickly the population would be in no risk of extinction whatsoever. Even if the numbers are significantly poorer, say only 10,000 women survive 26 years, the population would not be in serious risk of extinction and there would still be plenty of genetic diversity.
Ideally the daughters from each generation would mate with male offspring from one of the other 4 original men, this would greatly improve the diversity of Y-Chromosomes and eliminate inbreeding problems. The best strategy would probably be to have most the daughters migrate to another population as the first generation of sons would too valuable to risk losing on a long journey in a post-apocalyptic world.
If migration to another population is not possible the daughters should mate with the youngest generation available as the youngest generation will have the most genetic material from random women.
The real question is whether a society without male workers would hold itself together or catastrophically implode, however it would seem reasonable that at least millions of women would survive and even if such a breeding strategy is not perfectly employed the population would not generally go through a bottleneck (i.e. the population would never fall below 10,000 genetically distinct individuals and quite possibly wouldn't even fall below 10 million).