I'm the faculty search chair for a top-5 American computer science department.
How many publications, and of what quality would be required to get a job...?
This is simply the wrong question. To be considered for a position, you must have an independent research record among the very best in the world in your age cohort and subfield. The number of publications really doesn't matter, for the same reason grades don't matter for admission to a top PhD program; there are enough applicants with enough publications that we can afford to focus on more important features.
What matters more is the quality, visibility, impact, and reputation of your research. You must have a coherent and compelling research vision and agenda. You must have letters from the very best people in your field—people that the search committee already know by reputation, preferably not at your home institution. Those letters must say things like "major impact on the field" and "strongest student on the market this year", with specific, technical, and credible details to back up their opinions.
Moreover, the search committee must agree with the assessment in the reference letters. Without a champion on the search committee, you will not get an interview; there are simply too many strong applicants. Yes, we do read your statements, your papers, and other papers that cite your papers ourselves. We also call up colleagues in your field who didn't write you letters and ask them who the best people are in your field; they'd better mention you.
That gets you to the short list of people we are willing to interview. Unless it's a dry year, there are more people on this list than interview slots, so the recruiting committee has long discussions comparing the merits of various candidates and arguing about departmental needs/strategy. Sometimes enough clear winners emerge; more often, we just have to vote.
Once you are invited to an interview, your performance at the interview often becomes more important than your past record. Your talk must be compelling and polished. You must impress the faculty and students you meet with your breadth of expertise, your research agenda/vision, your likely success as an advisor, as a collaborator, as an instructor, and as an intellectual leader.
In short, it must be clear that you will get tenure.
Inevitably, more people will "pass" the interview than we have positions to offer. So there is another long and wide-ranging discussion among the faculty, comparing the merits of the various top candidates and arguing about departmental needs. Sometimes clear winners emerge; other times the faculty deadlock and the department head has to make the call.
I have seen candidates with 2 or 3 groundbreaking papers get hired (and later get tenure). I have also seen fresh PhDs with 20+ papers in top venues that were not even considered for an interview, because their work was judged incremental or narrow. The number of papers is simply not the right metric to care about.