I suspect I know the answer to this, but want to check as I hope I'm wrong.
We did a bunch of work on a branch and I had intended to merge this back with master as a rebase so that all of our history would be retained once all the pieces were in place. I put in a pull request and one of the reviewers approved it and did a "Squash and Merge". The merge was premature anyway and we reverted the changes on master but that left the new directories having a history on master. Now there is no option to "Rebase and Merge" (github has it greyed out). I tried to rebase the branch to master locally and it fails with errors pointing to the commit that deleted the previously merged files.
I've exhausted my git-fu. Is there a way out of this short of surgery on master and a forced push, which is unlikely to fly given the number of people who have the repo?
Is there a way out of this short of surgery on master
In one sense, no. There never was, from the moment of the so-called Squash and Merge (I say so-called because a Squash and Merge is not, in fact, any kind of a merge). What you did, revert, goes forward; it adds even more commits. The only way to "undo" actual history would be to reset. That is how you go backward. And the only way to do a reset on material that has already been pushed, is to force push.
However, I wouldn't say that all is lost, either. Sure, your history is a mess, but so what? At this, point that's just a glitch in the history; one day it will be lost in the sands of time. The important thing now is that master — meaning, the last commit on master before anyone does any more merging of any kind — should be in the right state (I mean, the right state of all your files). So just arrange that state, whatever it may be, and commit it right onto master, and carry on.
I would also like to say that I disagree with the premises of the question. You say:
I had intended to merge this [branch] with master as a rebase so that all of our history would be retained once all the pieces were in place
That's wrong. A "merge as a rebase" doesn't "retain the history". It lies about the history. The way to retain the history of a branch is to merge the branch, plain and simple. Rebase is not a merge; squash is not a merge; merge is a merge. Merges are good. They are the cleanest way to preserve what happened while making it possible for the future to progress neatly. (Just to give an example, if you had done a real merge, then if you discovered the merge was premature, you could just keep working on the branch, fix it, and merge it again. As things are, as you've discovered, that isn't so simple.)