It sounds like you're on the right track, taking advantage of the GBA's wrapping BGs to avoid having to shift the whole tilemap. The bigmap example from tonc-code.zip (edit: updated repo at libtonc-examples) has a working implementation of large scrolling tilemaps which you may find useful. There's also an annotated version of the same code which is much more readable.
I think you may just have an oversight with your vertical scrolling (it needs to start from the X offset of the horizontal scroll, after horizontal scrolling has been done?), because I'm doing similar in my game and it works fine, can scroll diagonally with no problem. Here's my code in case that's helpful, but it's not C. This is a bit of a tangent but it's based on the approach described in the GBA Resource Management article, which uses reference counting to dynamically unload tile gfx that are not in use (may be overkill for smaller games?), but other than that the basic approach of looping over rows & columns to copy in new sections of map data is the same.
Anyways, hope some of this helps, please shout if you're still running into issues!