[BETEPAH]

я так и хотел.
в 6 строке взять все элементы, а в 8 оставить только нужные.

У массива нет такого метода по умолчанию. Или прототипируйте или метод применяйте к элементу, а не к массиву. Да и не зачем массив держать ради одного элемента. У вас же на странице один body, надеюсь?

<div>
	<p>http://thumbs.wallbase.cc//locpereloc/thumb-filename.gif</p>
	<p>http://thumbs.wallbase.cc//locpereloc/thumb-filename2.gif</p>
</div>
<input type="button" id="replace" value="заменить" />
<script>
document.getElementById('replace').onclick = function(){
	var tag0 = document.getElementsByTagName('div')[0];
	var re0 = /http\:\/\/thumbs\.wallbase\.cc\/\/(.+?)\/thumb-(.+?)\.(.+?)/gi;
	tag0.innerHTML = tag0.innerHTML.replace(re0, 'http://wallpapers.wallbase.cc/$1/wallpaper-$2.$3');
}
</script>