Может попробовать уже готовые варианты?
Например
www.pagination.ru
А вообще гуглите в сторону -> pagination php
P.S. А если Ваше решение, то по идее, если мы сначала сохраним в переменную отсортированный массив, а потом будем его выводить, то он должен работать как надо.
Например:
$orderby = mysqli_query("SELECT * FROM `qq` ORDER BY `то по чем сотрируем`");
$page = $_GET['page'];
$i = 0;
while ($news = mysql_fetch_assoc($orderby)){
if ($i < 10*$page AND $i > 10*$page+10) {//10 можно в переменную, в которой будет количество записей на страницу.
echo $news;
}
$i++;
}