Update URL with new parameter value
I'm not sure about ways to improve performance, but I did notice a couple things.

Guaranteed Returns

If the specified key is already set to the specified value, your function does not return anything. Maybe this is the expected behavior, but I could see it being a problem if you used the function to directly update the URL.

window.location.href = changeURLParameter("thriggle","boring");
// If thriggle already == boring, this redirects you to /undefined


One way to fix that would be to simply remove the If statement if (aURLParams[sVariable] != sNewValue){...}. 

Without that check, regardless of whether the parameter is already set to the specified value, it'll be overwritten with the desired value and the URL string will be returned.

Original Sin

window.location.origin does not exist in older versions of Internet Explorer (9 and down). If your user base doesn't overlap with those poor souls still using IE9, feel free to ignore this one, but otherwise you could do something like this:

var sOrigin = window.location.origin ? window.location.origin : window.location.protocol + "//" + window.location.host;
sNewUrl = sOrigin + window.location.pathname;


Edit: even better, as you noted in your followup comment, just update window.location.search directly and you won't have to deal with window.location.origin!