With "New Sheets", the size limit is approximately 2 million cells in a Spreadsheet (not 4 million rows). Reference.
An example of creating a new Spreadsheet and setting it as a form destination is provided in the Forms Apps Script Reference:
var form = FormApp.openById('1234567890abcdefghijklmnopqrstuvwxyz');
var ss = SpreadsheetApp.create('Spreadsheet Name');
form.setDestination(FormApp.DestinationType.SPREADSHEET, ss.getId());
This more sophisticated evolution of that script can automatically create a new file when some pre-set goal is met (e.g. every 100 responses), and generate new file names consistent with Google Form naming conventions:
function checkResponseCount(e) {
var form = e.source;
var numResponses = form.getResponses().length;
if (numResponses % 100 == 0) {
startNewDestinationSpreadsheet();
}
}
function startNewDestinationSpreadsheet(ssName) {
var form = FormApp.getActiveForm();
var curDest = DriveApp.getFileById(form.getDestinationId());
var curName = curDest.getName();
if (!ssName || ssName === '') {
if (curName.search(/\(Responses.*\)/) == -1) {
ssName = curName+" (Responses 2)";
}
else if (curName.indexOf("(Responses)") !== -1) {
ssName = curName.replace("Responses","Responses 2");
}
else {
ssName = curName.replace(/(\d+)+/g, function(match, number) {
return parseInt(number)+1;
});
}
}
var newSheetId = SpreadsheetApp.create(ssName).getId();
form.setDestination(FormApp.DestinationType.SPREADSHEET, newSheetId);
Utilities.sleep(10000);
var sheet = SpreadsheetApp.openById(newSheetId).getActiveSheet();
sheet.deleteRows(2, sheet.getMaxRows()-2);
return newSheetId;
}
Caveat Emptor
There's a problem, though. When you set a spreadsheet as a destination for a form, all the existing responses get copied into the new destination. If your concern is that you'll run out of space in your destination spreadsheet, then this is obviously not going to help.
Because of that, the answer you don't want - copy the responses to another sheet - is really your best option.