What specifically do you need it to do that it isnt' doing now? I ask because it might not be more power that you need, or at least not simply that.
If you do just need more power, then there are a couple ways:
If the controller has parts in it capable of higher voltage *and* does not have an HVC that causes it to shutdown if the voltage is higher than the 42v it expects maximum from a 36v battery, you can use a 48v battery (54v full) instead of 36v, for instance, to get a third more total power (volts x amps = watts). If you're considering replacing the controller anyway, then if it fails from using it at the higher voltage, it's not a big loss...but it is generally possible to look inside at certain parts of the controller and guess if it will work at the higher voltage reliably. (still a guess, until it's tested, though). Replacing the battery is the most expensive option.
Note that higher voltage also means higher speed for the same throttle setting (if it is throttle capable; if it's just a speed-limit-per-assist-level PAS system it will still be limited to the same speed on each assist level).
If the 36v battery itself can handle higher current output than it does with the existing controller, you could also just replace the controller with one that has a higher current limit. This is the cheapest option.
Note that the motor itself will likely handle a little more power continuously; how much depends on what exactly it is. A link to the kit might help us figure out what the parts are capable of, if we've seen them before.
Adding a battery in series with the existing battery may work fine, however, if the BMS on either battery has FETs that can't handle the voltage of both batteries in series, they may fail when the BMS shuts down for any reason. If they fail, either of these may happen: The FEts may fail stuck on, so the BMS can no longer turn off the output, and can't protect the battery against overdischarge / overcurrent, etc. The FETs may fail open, so the battery appears dead (no voltage). These can be prevented with some external electronics if necessary.
If the FETs on both batteries in series can handle the voltage of the full pack, then they shoudl work fine in series. However, the add-on battery must be able to handle the same or higher amount of current (amps, A) as the original, and have the same or greater capacity (amp-hours, Ah), or the system will either not perform as well as it should for the former, and wont' have the range it should for the latter.
