I found the issue and I will fix it in root trunk.
It is easy to bypass by adding a first graph. The problem shows up because you have only one graph.
{
const UInt_t N=100000;
Double_t x[N];
Double_t y[N];
for(int i=0;i<N;i++) {x[i]=i;y[i]=i+1;}
TMultiGraph* mg = new TMultiGraph("mg","mg");
TGraph* g1 = new TGraph(1); g1->SetPoint(0,0.,0.); mg->Add(g1);
TGraph* gr = new TGraph(100000,x,y);
mg->Add(gr);
mg->Draw("a*");
cout<<mg->GetXaxis()->GetNbins()<< " "<< gr->GetXaxis()->GetNbins() <<endl;
}