It's not supposed to delete them.
Your local branches—which really should just be called "your branches"—are yours. Only your remote-tracking names, origin/* in this case, are not yours.1 So if origin had a branch named xyzzy earlier, but doesn't any more, git fetch --prune origin or git remote prune origin deletes your origin/xyzzy to match origin's lack-of-xyzzy.
It doesn't touch your branches, which are yours. If you are sure that they can go now, you'll have to delete them yourself. People have written scripts to do this, but said scripts tend to be dumb: they will often delete your xyzzy even if you have commits you forgot to push before mergiing, or meant to move to another branch, and once your xyzzy is deleted, it's often too late. So be careful with such scripts.
(It might be nice to have an option to these commands that tells them: If I have a local branch xyzzy that points to the same commit as origin/xyzzy, and you're deleting origin/xyzzy, delete my local xyzzy too. Moreover, if I have xyzzy, but origin/xyzzy does not match my xyzzy, complain and stop, so that I can figure out what to do about this. But they do not have such an option.)
1Technically, these are yours, too. It's just that your Git is set up so that when your Git calls up their Git—the one at origin—and gets branch names and hash IDs from them, your Git overwrites your own origin/master with their updated master. So while origin/master is a name in your Git repository's "name-to-hash-ID" database, it's not a name you would normally control yourself. You just let your Git mirror their Git, with their master becoming your origin/master.
Or, to say it shorter: your Git's origin/master is your Git's way of remembering their Git's master. So it's sort-of theirs.