Why do we say "of mine/of his" instead of "of me/of him"?

They're examples of the double genitive/possessive, which is perfectly valid and has been around in English for centuries. The of already denotes "possession", but we do this again when we use mine/his instead of me/him.

The fact that we don't say John is a friend of me/him is really just idiomatic for those particular forms. But that "idiomatic principle" isn't universally observed - people often say, for example, He's a friend of John. Though they also say a friend of John's - both forms are valid there.

Here's an NGram showing how friend of her has gradually given way to friend of hers over the past couple of centuries, as the "reach" of the idiomatic mine/his has been extended.