Actually it is an extensive quantity, but not in the way extensive is used in classical thermodynamics. It is proportional to area and not mass (or equivalently for a classical object, volume). Entropy is normally (but not always) proportional to mass, or energy, which is approximately proportional to the number of elementary particles and thus the number of possible states. For a black hole (BH), the number of possible states is proportional to the number of different Planck areas there are in the BH horizon. i.e., the states information is as though it was stored in the horizon, not the bulk
We don't know how to calculate the entropy of a singularity, the physics breaks down and it requires quantum gravity to calculate it. But Hawking has calculated the temperature of a BH, through his calculations, where he discovered that a BH radiates as a black body at a given temperature given by the inverse of its mass. From there it is easy to get the entropy.
The simplistic version then is that since $dS = dQ/T$, with $Q$ the heat absorbed by the BH and $T$ its black body radiation-equivalent temperature, if you take Hawking's result as $T = k/M$ for some constant $k$, then $dS = kMdQ$. Since the heat absorbed into the BH is energy, it increases the BH mass (in natural units) as $dQ = dM$. So, substituting, $dS = kMdM$, and then integrating $S = kM^2$. You can see other derivations, but when Hawking found his BH radiation temperature dependent on mass, there's then no two ways around it that they could think of, nor anybody else so far.
This of course was proven by Hawking-Bekenstein based on finding that the Hawking radiation is black body with temperature proportional to the so called surface gravity at the horizon, which is inversely proportional to the BH mass, and with Bekenstein then led to entropy proportional to the horizon area, and in fact equal to the number of Planck areas multiplied by $k_b/4$ ($k_b$ is the Boltzmann constant), as per the Hawking-Bekenstein equation, also discussed in @Heather’s answer, and written (slightly off) in the question. This relates BH entropy and physics to thermodynamics – and indeed BH entropy can grow or stay the same, but never decrease, by the second law of thermodynamics. The two BH’s which merged on 9/14/15 had a final entropy greater than the sum of the two before, plus some entropy was radiated away in the gravitational radiation. The BH entropy laws also lead to equations for the maximum energy that may be extracted from merging BH’s. Bekenstein also showed that BH entropies are the maximum entropy possible for any volume of space with the same volume as the BH.
But the question still remains: why, and how? How is it that the possible states of the BH are encoded in the horizon, if indeed the statistical interpretation holds? For only if it holds would the statistical interpretation be on firm ground, regardless of the thermodynamic relationships. So there’s been attempts and some success (but no proof or certainty yet) in two separate results in physics.
One is the Holographic principle by 't Hooft and Susskind, and others, now a few years old, and still no proof, but some ocassional developments on it. They conjecture that the quantum gravity solution of a spacetime in d+1 dimensions is in a 1-1 correspondence to a Conformal Field Theory (CFT) without gravity, in the d dimensional boundary of the spacetime.
They based this on generalizing the proven results of the AdS/CFT correspondence found by Maldacena and others, who proved the results for a string quantum gravity in anti-de Sitter (AdS) spacetime. AdS see is a vacuum solution of the Einstein Field Equations with a negative cosmological constant (de Sitter is with a positive cosmological constant, the limit of our known universe as its age goes to infinity and the cosmological constant completely dominates). The AdS/CFT correspondence is also called gauge/gravity duality, gauge for the CFT. CFT’s are quantum field theories.
The Holographic conjecture and the AdS/CFT correspondence have led people to think that information on the quantum states of the bulk, in some cases or in general, is stored in its boundaries. Or surfaces, similar to the way holography works for a 3D object. But there are also some counter-examples, and so in general it is still an interesting approach, but not well understood or accepted. Still, if the general case is valid, the ideas is that the states of the BH would be encoded, or imprinted, on its horizon. Possibly that could provide a mechanism for the matter/energy that falls in, and the quantum information that was thought lost to the BH, to be in the horizon and not lost, and possibly later encoded in the Hawking blackbody (with something extra then) radiation.
There is another more recent finding that indicates that the information on the state of the BH may be stored at the horizon. It’s by Hawking, Perry and Strominger, from January of 2016. See the paper in arXiv, and the Phys. Rev. article in June 2016 (I’ve not read the Phys Rev version but the abstracts are the same).
What they claim is new, and based on new re-discovered asymptotic symmetries at conformal infinity. They claim that based on those symmetries BH's have conserved quantities, they call soft hair. That is, that BH’s have some hair that is over and beyond the mass, angular momentum and charge proved by Hawking years ago. Where it is not the same he 'proved' before (yes, there's reason this new symmetries break on of his assumptions back then, that the vacuum was non-degenerate, was unique) is that BHs actually have what the authors call soft hair, very low energy hair that in the limit is zero energy, but still is there. The soft hair is due to soft photons or soft gravitons, that reside in the horizon. They claim that, from part of their abstract:
This Letter gives an explicit description of soft hair in terms of soft gravitons or photons on the black hole horizon, and shows that complete information about their quantum state is stored on a holographic plate at the future boundary of the horizon. Charge conservation is used to give an infinite number of exact relations between the evaporation products of black holes which have different soft hair but are otherwise identical. It is further argued that soft hair which is spatially localized to much less than a Planck length cannot be excited in a physically realizable process, giving an effective number of soft degrees of freedom proportional to the horizon area in Planck units.
Thus they claim they have argued or shown that the entropy is due to the degrees of freedom, or possible states of, the horizon, in accord with BH thermodynamics. Still, they do state, in the body of the arXiv paper, that they have not proven that indeed there’s enough degrees of freedom to really store all the information, and that work remains. Their degrees of freedom, or the soft hair, comes from new symmetries that they re-discovered on the conformal infinity of asymptotically flat spacetime (think of a BH in asymptotically flat spacetime), and which lead to new conserved quantities, the soft hair. Since the BH horizon is one boundary of the asymptotically flat spacetime (i.e., outside the horizon), they show using Penrose diagrams and can calculate the conserved soft hair over the BH horizon.
The soft ‘charges’ (the conserved entities of the symmetries) they re-discovered had been identified by Weinberg in 1965, based on conformal symmetries at infinity called the BMS symmetries (Bondi, actually also van der Burg, Metzner and Sachs), found and published by those first 3 in a paper, and Sachs in another, in 1962. See the Living Reviews article. Those 4 demonstrated in 1962 that there are additional symmetries at conformal infinity in asymptotically flat spacetime, besides the Poincare group. The BMS group was also used by them to define the BMS mass, in asymptotically flat spacetime, at conformal infinity. They found a family of symmetries called supertranslations, and another called superrotations, generalizations of the Poincare group which also inlcudes it, basically coming out of the conformal invariant structure. They also found that those symmetries were non-trivial, that were physical, and cannot be transformed away. Those symmetries turns out were an infinite set of diffeomrphisms, and lead to the soft hair. They occur for gravitational fields and for electromagnetic fields, so for soft photons and gravitons. Hawking et al. did their calculations for electromagnetic fields in a BH, but argued for the same effect for the gravitational field. They admit there’s still a lot to calculate.
So, the most promising (with all the unknowns and unproven theories yet) explanations for the entropy of a BH to be proportional to the horizon area is that the information on the state of the BH, at a quantum level, is imprinted in its horizon. If so it has to be proportional to area and not mass.
[BTW, a personal aside, I’m proud to have had Sachs as my advisor in General Relativity, but it was about 5-6 years later, and he was not doing the gravitational wave work he did earlier anymore, not of course did I]