Although I favor a recall process, too, the problem here is that you stated a majority of voters (which would mean a majority of REGISTERED voters). That would be almost impossible to get via petitions, since a majority of those said voters would not have cast a vote to begin with (maybe getting 50%+1 vote of those who cast a vote for Senator in that last election).
Also, if you had a hostile legislature to said Senator (think of Scott Brown in Massachusetts - elected by the people when 90% of the legislature was Demonrat), you could easily get retaliatory recalls (and you know they’d almost exclusively be directed at Republicans).