If you want to add rel=prev and rel=next for SEO purpose and high ranking of your website. Than follow easy step to add rel=prev and rel=next to Magento product pagination.

ex.
<link rel="prev" href="http://www.example.com/store.html?p=2">
<link rel="next" href="http://www.example.com/store.html?p=4">

Update: Issue solved when filtering product list

1. So, if you didn’t already modified head.phtml file, create identical directory hierarchy and copy/paste head.phtml in your theme or package.

Path example if using package:
..\app\design\frontend\[your_package_name]\default\template\page\html\head.phtml

Path example if using theme:
..\app\design\frontend\default\[your_theme_name]\template\page\html\head.phtml

2. Add code below to head.phtml at the bottom of file.

$actionName = $this->getAction()->getFullActionName();
if ($actionName == 'catalog_category_view') // Category Page
{
     $category = Mage::registry('current_category');
     $prodCol = $category->getProductCollection()->addAttributeToFilter('status', 1)->addAttributeToFilter('visibility', array('in' =>     array(Mage_Catalog_Model_Product_Visibility::VISIBILITY_IN_CATALOG,   Mage_Catalog_Model_Product_Visibility::VISIBILITY_BOTH)));
     $tool = $this->getLayout()->createBlock('page/html_pager')->setLimit($this->getLayout()->createBlock('catalog/product_list_toolbar')->getLimit())->setCollection($prodCol);
     $linkPrev = false;
     $linkNext = false;
     if ($tool->getCollection()->getSelectCountSql()) {
     if ($tool->getLastPageNum() > 1) {
     if (!$tool->isFirstPage()) {
     $linkPrev = true;
     if ($tool->getCurrentPage() == 2) {
     $url = explode('?', $tool->getPreviousPageUrl());
     $prevUrl = @$url[0];
     }
     else

    {
          $prevUrl = $tool->getPreviousPageUrl();
     }
  }
  if (!$tool->isLastPage()) {
  $linkNext = true;
  $nextUrl = $tool->getNextPageUrl();
 }
 }
}
if ($linkPrev) echo '<link rel="prev" href="' . $prevUrl . '" />';
if ($linkNext) echo '<link rel="next" href="' . $nextUrl . '" />';
}