It is the Governor General that holds the legal power. The Prime Minister plays a political role. According to an unwritten rule, a constitutional convention, the legal power belongs to the Governor General. It is the Governor General who decides. In a classic situation, the Governor General grants the Prime Minister prorogation in response to the latter's advice. However, the Governor General is empowered to act independently — even going against the Prime Minister — in extreme circumstances. It is difficult to imagine extreme circumstances, but if the Prime Minister was motivated by financial interests or was proven to be corrupt, for example, the Governor General could reject his request.
On April 27th, 2010. See this statement in context.