Let met just get some stray observations out of the way: "Professor Bigshot" publishes a paper with flaws that are obvious to a PhD student, who knows just how to fix them and happens to know information about the status of Professor Bigshot's submissions. This "gossip" seems perhaps a smidge unseemly (although I don't want to claim that I never talk about this sort of thing myself). In my field, well known senior researchers rarely write papers with an obvious shoddy aspect (they may make some kind of subtle, critical mistake -- everyone does sometimes -- but that's not the same thing). I find it a bit curious, but it doesn't affect my answer.
Sure, if you and someone else have two unpublished manuscripts that would each benefit from being combined with the other, you should suggest the combination. I would have given the same suggestion already given in the comment: maybe get your advisor to broach the subject. The advantage of this is that your advisor is (surely?) much more senior and established than you, so if the request comes from him in the formal sense, it comes with his imprimatur. Putting myself in the Professor B's place, knowing that your advisor has endorsed the action is at least useful information. If your advisor is someone I know and respect, then that does put more gravity behind the request.
(By the way, you didn't just wake up one day with a "followup paper" on your hands. In deciding to write the paper, you knew you would be putting yourself in your current situation. I hope that when a PhD student decides to write a new paper, he mentions it to his advisor! What advice did you get while you were writing the paper?)
I don't mean to insist that going through your advisor is a key point. Given that you have already corresponded with Professor B, it most likely will not be. Anyway, let me assume that you will do the asking yourself, because that's the more difficult case.
How do I go about suggesting to Prof. Bigshot that we merge our papers?
Assuming you want to do it yourself (to be sure, there is nothing wrong with doing this), you write to Professor Bigshot, send him a copy of your paper, and ask for his feedback on it. You mention that the possibility of merging them has occurred to you, and you would be interested to hear his take on that.
I don't know what the etiquette for this situation is.
I don't think there is any specific protocol here. In dealing with academics, especially senior academics, you want to be (i) informative, (ii) respectful and (iii) reasonably concise. There are many ways to do so.
I worry that he will think I am trying to take credit for his idea.
Suggesting coauthorship is not trying to take credit for someone else's idea. It is possible that he thinks that the idea is so precious, even with its shoddy implementation, that he doesn't want to share authorship with someone else. Okay, he can say no, but you haven't done anything wrong. It would also be possible, by the way, to describe your respective contributions in the paper itself, in this case crediting Professor B with the idea and you with the implementation. That is not done as much as it should be, but it is sometimes done. But wait -- in this case you have separate arxiv preprints, so the origin of the contributions is rather publicly known. I don't see that you have much to worry about. If you wanted to, you could cite both preprints in the paper: this would be an unobtrusive, easy way to show any interested party the provenance of the paper.
Should I just wait for him to bring it up? or should I actively suggest it?
You should actively call his attention to the possibility of the collaboration. There is no prize for the meek here.
