Sharepoint - REST Api error "Server relative urls must start with SPWeb.ServerRelativeUrl"

Try removing the / character from the beggining of the parameter of GetFolderByServerRelativeUrl function. Change it to: 'testDocumentList/testFolder'.

Your updated code should look like this:

var url = String.format(
            "{0}/_api/web/GetFolderByServerRelativeUrl('testDocumentList/testFolder')/Files/Add(url='{1}', overwrite=true)",
            _spPageContextInfo.webAbsoluteUrl, fileName);

In my case, I was having this error in SharePoint Online. My site collection URL contains "/sites". So to fix this issue I have to pass URL as follow:

var requesturi= "";
    if((_spPageContextInfo.webAbsoluteUrl) && (_spPageContextInfo.webAbsoluteUrl.indexOf("sites")>0))
    {
        requesturi = _spPageContextInfo.webAbsoluteUrl + "/_api/web/GetFileByServerRelativeUrl('"+_spPageContextInfo.webServerRelativeUrl+"/Shared%20Documents/document.docx')/$value";
    }
    else
    {
        requesturi = _spPageContextInfo.webAbsoluteUrl + "/_api/web/GetFileByServerRelativeUrl('/Shared%20Documents/document.docx')/$value";
    }