I know this is going to sound silly, but it is something I stumbled onto while coding something just today, as a matter of fact, and it drove me nuts.
if($page > 1){
$prev = ($page - 1);
echo "<a href=\"".$_SERVER['PHP_SELF'].
"?page=$prev&searchValue=$searchValue\"><<Previous</a> ";
}
Where you have your $_SERVER['PHP_SELF'] variable, try putting the page name. (Just to test it out) so change it to:
if($page > 1){
$prev = ($page - 1);
echo "<a href=\"whatever.php?page=$prev&searchValue=$searchValue\"><<Previous</a> ";
}
This is really to test things out and get the help ball rolling here. I was working on something and my variable kept hanging around (for a reason I am trying to find) when I was trying to use the variable like you, but when I hard coded the page's name, it worked. Let's rule that in or out first.
Secondly, try echoing your $prev and $page values, to see what they are showing as... If your $prev variables equals 1, then you know why it's going back to page 1, and then we need to start looking at why it is valued at 1.