http://www.h-o.nl/blog/display-related-products-with-working-product-count-and-pagination/

catalog.xml

<block type="catalog/product_list_related" name="catalog.product.related" template="catalog/product/list/related.phtml">
	<block type="catalog/product_list_toolbar" name="product_list_toolbar" template="catalog/product/list/toolbar.phtml">
		<block type="page/html_pager" name="product_list_toolbar_pager"/>
		<action method="addPagerLimit"><mode>list</mode><limit>20</limit></action>
	</block>
	<action method="setToolbarBlockName"><name>product_list_toolbar</name></action>
</block>

Related.php

<?php

class Mage_Catalog_Block_Product_List_Related extends Mage_Catalog_Block_Product_Abstract
{
    /**
     * Default toolbar block name
     *
     * @var string
     */
    protected $_defaultToolbarBlock = 'catalog/product_list_toolbar';

    /**
     * Product Collection
     *
     * @var Mage_Eav_Model_Entity_Collection_Abstract
     */
    protected $_productCollection;

    /**
     * Retrieve loaded category collection
     *
     * @return Mage_Eav_Model_Entity_Collection_Abstract
     */
    protected function _getProductCollection()
    {
        
        	if (isset($_GET['p'])) {$page = $_GET['p'];}else{$page = 1;};
	        $product = Mage::registry('product');
	        /* @var $product Mage_Catalog_Model_Product */
	
	        $this->_itemCollection = $product->getRelatedProductCollection()
	            ->addAttributeToSort('name', 'asc')
	            ->addStoreFilter()
	            ->setPage($page,20)
	        ;

	        $this->_addProductAttributesAndPrices($this->_itemCollection);
	
			Mage::getSingleton('catalog/product_status')->addSaleableFilterToCollection($this->_itemCollection)->addVisibleFilterToCollection($this->_itemCollection);
	        Mage::getSingleton('catalog/product_visibility')->addVisibleInCatalogFilterToCollection($this->_itemCollection);

	        foreach ($this->_itemCollection as $product) {
	            $product->setDoNotUseCategoryId(true);
	        }
        
         	$this->_productCollection = $this->_itemCollection;
        
        return $this->_productCollection;
    }


    /**
     * Retrieve loaded category collection
     *
     * @return Mage_Eav_Model_Entity_Collection_Abstract
     */
    public function getLoadedProductCollection()
    {
        return $this->_getProductCollection();
    }

    /**
     * Retrieve current view mode
     *
     * @return string
     */
    public function getMode()
    {
        return $this->getChild('toolbar')->getCurrentMode();
    }

    /**
     * Need use as _prepareLayout - but problem in declaring collection from
     * another block (was problem with search result)
     */
    protected function _beforeToHtml()
    {
        /*$toolbar = $this->getLayout()->createBlock('catalog/product_vergelijker_toolbar', microtime());
        if ($toolbarTemplate = $this->getToolbarTemplate()) {
            $toolbar->setTemplate($toolbarTemplate);
        }*/
        $toolbar = $this->getToolbarBlock();

        // called prepare sortable parameters
        $collection = $this->_getProductCollection();

        // use sortable parameters
        if ($orders = $this->getAvailableOrders()) {
            $toolbar->setAvailableOrders($orders);
        }
        if ($sort = $this->getSortBy()) {
            $toolbar->setDefaultOrder($sort);
        }
        if ($modes = $this->getModes()) {
            $toolbar->setModes($modes);
        }

        // set collection to tollbar and apply sort
        $toolbar->setCollection($collection);

        $this->setChild('toolbar', $toolbar);
        Mage::dispatchEvent('catalog_block_product_vergelijker_collection', array(
            'collection'=>$this->_getProductCollection(),
        ));

        $this->_getProductCollection()->load();
        Mage::getModel('review/review')->appendSummary($this->_getProductCollection());
        return parent::_beforeToHtml();
    }

    /**
     * Retrieve Toolbar block
     *
     * @return Mage_Catalog_Block_Product_Vergelijker_Toolbar
     */
    public function getToolbarBlock()
    {
        if ($blockName = $this->getToolbarBlockName()) {
            if ($block = $this->getLayout()->getBlock($blockName)) {
                return $block;
            }
        }
        $block = $this->getLayout()->createBlock($this->_defaultToolbarBlock, microtime());
        return $block;
    }

    /**
     * Retrieve list toolbar HTML
     *
     * @return string
     */
    public function getToolbarHtml()
    {
        return $this->getChildHtml('toolbar');
    }

    public function setCollection($collection)
    {
        $this->_productCollection = $collection;
        return $this;
    }

    public function addAttribute($code)
    {
        $this->_getProductCollection()->addAttributeToSelect($code);
        return $this;
    }

    public function getPriceBlockTemplate()
    {
        return $this->_getData('price_block_template');
    }

    /**
     * Retrieve Catalog Config object
     *
     * @return Mage_Catalog_Model_Config
     */
    protected function _getConfig()
    {
        return Mage::getSingleton('catalog/config');
    }

    /**
     * Prepare Sort By fields from Category Data
     *
     * @param Mage_Catalog_Model_Category $category
     * @return Mage_Catalog_Block_Product_Vergelijker
     */
    public function prepareSortableFieldsByCategory($category) {
        if (!$this->getAvailableOrders()) {
            $this->setAvailableOrders($category->getAvailableSortByOptions());
        }
        $availableOrders = $this->getAvailableOrders();
        if (!$this->getSortBy()) {
            if ($categorySortBy = $category->getDefaultSortBy()) {
                if (!$availableOrders) {
                    $availableOrders = $this->_getConfig()->getAttributeUsedForSortByArray();
                }
                if (isset($availableOrders[$categorySortBy])) {
                    $this->setSortBy($categorySortBy);
                }
            }
        }


        return $this;
    }
}

relatedTemplate.php

<div class="block block-related">
    <div class="block-title">
        <strong><span><?php echo $this->__('Related Products') ?></span></strong>
    </div>
    <div class="block-content">
        <?php echo $this->getToolbarHtml() ?>
        <p class="block-subtitle"><?php echo $this->__('Check items to add to the cart or') ?>&nbsp;<a href="#" onclick="selectAllRelated(this); return false;"><?php echo $this->__('select all') ?></a></p>
        <ol class="mini-products-list" id="block-related">
       <?php foreach ($_productCollection as $_product): ?>
            <li class="item">
                <?php if(!$_product->isComposite() && $_product->isSaleable()): ?>
                    <?php if (!$_product->getRequiredOptions()): ?>
                        <input type="checkbox" class="checkbox related-checkbox" id="related-checkbox<?php echo $_product->getId() ?>" name="related_products[]" value="<?php echo $_product->getId() ?>" />
                    <?php endif; ?>
                <?php endif; ?>
                <div class="product">
                    <a href="<?php echo $_product->getProductUrl() ?>" title="<?php echo $this->htmlEscape($_product->getName()) ?>" class="product-image"><img src="<?php echo $this->helper('catalog/image')->init($_product, 'thumbnail')->resize(50) ?>" width="50" height="50" alt="<?php echo $this->htmlEscape($_product->getName()) ?>" /></a>
                    <div class="product-details">
                        <p class="product-name"><a href="<?php echo $_product->getProductUrl() ?>"><?php echo $this->htmlEscape($_product->getName()) ?></a></p>
                        <?php echo $this->getPriceHtml($_product, true, '-related') ?>
                        <?php if ($this->helper('wishlist')->isAllow()) : ?>
                            <a href="<?php echo $this->getAddToWishlistUrl($_product) ?>" class="link-wishlist"><?php echo $this->__('Add to Wishlist') ?></a>
                        <?php endif; ?>
                    </div>
                </div>
            </li>
        <?php endforeach ?>
        </ol>
        <script type="text/javascript">decorateList('block-related', 'none-recursive')</script> 
    	<?php echo $this->getToolbarHtml() ?>
    </div>
</div>