I don't have experience of Brightpay, but have used Moneysoft payroll for the past couple of years and I have found it to be good value, easy to use and it does everything I've needed to do, so can highly recommend that.
In terms of charging, I do charge by the number of payslips, but my clients are mainly very small. I charge a fee for the first employee (most only have one) and then half that rate for additional employees. I have a client whose business is very seasonal, so it works, as he can have between about 4 and 12 employees to pay, depending on the time of year. I also sort out any issues that may arise with HMRC without charging extra, so clients do feel they are not just being charged every time they do anything.
Hope this helps