In most of the Battle Frontier areas, the BP gain increases after every other battle. I find the Battle Pike or the Battle Pyramid to be the quickest way to gain BP (with the Pike, you can possibly fight up to 7 trainers, or more with double battles, but sometimes less. In the Pyramid you gain 5 BP per succesful set of 7, although this does take it's time - much easier at L50 than L100).
Also note the Battle Tower is the exception to this, where you gain 1 BP, then the gain increases by 1 per floor (so second time you would win 2 BP, third time you would win 3 BP, etc). On other areas, you have a base starting value, which increases by 1 every two floors. The Battle Pike starts at 3 BP, and increases by 1 every two successful round (so it goes 3, 3, 4, 4, 5, etc). The Frontier Brains give you a good amount too, usually between 12 and 20.
Also, go to the house somewhat south-east of the Battle Pyramid and place bets. You can bet 5, 10 or 15 BP, but if you win the area you are going to, you get double back (plus the BP you won from beating that area). They sometimes send you to obscure areas, like Battle Factory Double Battles, but if you don't do these areas often you will face the lower tier set of Pokemon (unevolved and NUs) so those bets can be placed with confidence.