How does HIV survive natural selection? And how has it managed to kill far more than any non-airborne virus in recorded history?
Human Immunodeficiency Virus is a mutated form of Simian Immunodeficiency Virus. In simians (Apes and Monkeys, not including humans), SIV is not pathogenic, in most cases, however, when the mutated form made the jump to humans, it became highly contagious and virulent. You can find a basic description in the wikipedia article here: Simian Immunodeficiency virus.
As for your second question, I would likely say that influenza has killed more humans in total than HIV, so you would have to provide a reference for your claim.
However, because HIV is a retrovirus that incorporates into the genome of the immune cells of its host, it can survive in the body for long periods of time in a dormant state. A person may not know they are infected for months or years, and they can pass the virus on to other people. Slow killing viruses such as HIV are very dangerous, as they can be transmitted to large swaths of the population before people are aware they are sick.
Based on comments, there may be a misunderstanding of the term virulence. From The Karolinska Instetutet medical subject heading (MeSH) definition:
The degree of pathogenicity within a group or species of microorganisms or viruses as indicated by case fatality rates and/or the ability of the organism to invade the tissues of the host. The pathogenic capacity of an organism is determined by its VIRULENCE FACTORS.
-The Karolinska Institutet; Virulence
The emphasis is mine, but virulence also refers to the ability of the virus to infect its host, and does not necessary lead to the hosts death. The virus that causes the common cold is highly virulent, but for almost the entire human population it causes nothing more than discomfort.
A virus like Ebola on the other hand is highly virulent in both senses of the term. The reason that there are far fewer cases of Ebola is that it kills the human host so quickly, that an afflicted person will on average only go on to infect about two other individuals, mainly because victims 1) die quickly, 2) are only contagious after symptoms manifest themselves, and 3) requires direct contact with the infected person's bodily fluids.
Contrast that with Influenza which a single person can infect tens to hundreds of people and is contagious before they are displaying symptoms and spreads it with casual contact, or as stated above, with HIV, where a person can be contagious for weeks, months, or even years before they are aware that they are infected, and you see why HIV is very sustainable in the Human population.
HIV also has the added weapon in its arsenal that it can lay dormant in cells for long periods of time so as to escape the detection of the host immune system, and as the disease attacks and kills immune cells, when the dormant virus activates again there are far fewer specialized cells to address the active infection.
Another thing is it is the comorbidity with other diseases that often results in the death of a patient with an HIV infection. AIDS results from other diseases having the opportunity to go unchecked after HIV has decimated the host immune system.