Edit History

Ok, I think I made it but presentation layer is up to You. I won't cover basics of overrides here, I'll just post changes and addition in functions. If You know PS Basics then You will make it. This doesn't support pagination. Basically it is quite simple to do but it just looks hard.

We need to edit only 3 files: Search.php, SearchController.php and Search.tpl from theme folder.

First thing we need create function to search in categories so let's go Search.php (You can create an override for this) with this function in it.

 public static function findCategories($expr, $id_shop = 1, $id_lang = 1, $order_by = 'id_parent', $limit = 15, $search_in_keywords = false)
    {
        $db = Db::getInstance(_PS_USE_SQL_SLAVE_);
        $expr = pSQL(Tools::substr($expr, 0, PS_SEARCH_MAX_WORD_LENGTH));
        $keywords_search = ($search_in_keywords) ? 'OR cl.meta_keywords LIKE \'%'.$expr.'%\'' : '';

        $query = '
            SELECT * FROM '._DB_PREFIX_.'category_lang cl
            LEFT JOIN '._DB_PREFIX_.'category c ON cl.id_category = c.id_category
            LEFT JOIN '._DB_PREFIX_.'category_shop cs ON cs.id_category = cl.id_category
            WHERE (cl.name
            LIKE \'%'.$expr.'%\' '.$keywords_search.')
            AND cl.id_lang = '.(int)$id_lang.'
            AND c.active = 1
            AND cs.id_shop = '.(int)$id_shop.'
            ORDER BY c.'.pSQL($order_by).'
            LIMIT '.(int)$limit.'
        ';

        if ($results = $db->executeS($query))
            return $results;
        else
            return false;
    }

Now let's go to SearchController.php and look for public function initContent() function (as stated before - you can create override of it) and search for this line 

[...] 
} elseif (($query = Tools::getValue('search_query', Tools::getValue('ref'))) && !is_array($query)) {
            $this->productSort();
            $this->n = abs((int)(Tools::getValue('n', $product_per_page)));
            $this->p = abs((int)(Tools::getValue('p', 1)));
            $original_query = $query;
            $query = Tools::replaceAccentedChars(urldecode($query));
            $search = Search::find($this->context->language->id, $query, $this->p, $this->n, $this->orderBy, $this->orderWay);
           
            if (is_array($search['result'])) {
                foreach ($search['result'] as &$product) {
                    $product['link'] .= (strpos($product['link'], '?') === false ? '?' : '&').'search_query='.urlencode($query).'&results='.(int)$search['total'];
                }
            }

			Hook::exec('actionSearch', array('expr' => $query, 'total' => $search['total']));
            $nbProducts = $search['total'];
            $this->pagination($nbProducts);

            $this->addColorsToProductList($search['result']);

            $this->context->smarty->assign(array(
                'products' => $search['result'], // DEPRECATED (since to 1.4), not use this: conflict with block_cart module
                'search_products' => $search['result'],
                'nbProducts' => $search['total'],
                'search_query' => $original_query,
                'homeSize' => Image::getSize(ImageType::getFormatedName('home'))));
        }

and change it to this:

elseif (($query = Tools::getValue('search_query', Tools::getValue('ref'))) && !is_array($query)) {
            $this->productSort();
            $this->n = abs((int)(Tools::getValue('n', $product_per_page)));
            $this->p = abs((int)(Tools::getValue('p', 1)));
            $original_query = $query;
            $query = Tools::replaceAccentedChars(urldecode($query));
            $search = Search::find($this->context->language->id, $query, $this->p, $this->n, $this->orderBy, $this->orderWay);
            $search_cats = Search::findCategories($query, $this->context->shop->id, $this->context->language->id, 'id_parent', 15, false); // added by Eryk
            if (is_array($search['result'])) {
                foreach ($search['result'] as &$product) {
                    $product['link'] .= (strpos($product['link'], '?') === false ? '?' : '&').'search_query='.urlencode($query).'&results='.(int)$search['total'];
                }
            }

			Hook::exec('actionSearch', array('expr' => $query, 'total' => $search['total']));
            $nbProducts = $search['total'];
            $this->pagination($nbProducts);

            $this->addColorsToProductList($search['result']);

            $this->context->smarty->assign(array(
                'products' => $search['result'], // DEPRECATED (since to 1.4), not use this: conflict with block_cart module
                'search_products' => $search['result'],
                'search_cats' => $search_cats, // added by Eryk
                'nbProducts' => $search['total'],
                'search_query' => $original_query,
                'homeSize' => Image::getSize(ImageType::getFormatedName('home'))));
        }

Now in search.tpl from You theme folder You need to display these values but I won't help You with bad look - I created this only for myself and for my theme so You need to adjust it with Your html + smarty.

Right after 

{include file="$tpl_dir./errors.tpl"}

add this code

{if isset($search_cats) && $search_cats}
    <div id="categories">
        <hr>
        <h3 class="t18"><strong>{l s='Categories found'} ({$search_cats|@count} results)</strong></h3>
        {if $nbProducts > 0}
            <p class="lighter">You will find founed products below categories results.</p>
        {/if}
        <ul class="clearfix row">
        {foreach from=$search_cats item=category name=cat}
            <li class="col-xs-6 col-lg-3">
                <div class="product-container">
                    <a href="{$link->getCategoryLink($category.id_category, $category.link_rewrite)|escape:'html':'UTF-8'}" title="{$category.name|escape:'html':'UTF-8'}" class="img">
                        {if $category.id_category}
                            <img src="{$img_cat_dir}{$category.id_category}_thumb.jpg" alt="{$category.name|escape:'html':'UTF-8'}" width="{$mediumSize.width}" height="{$mediumSize.height}" class="img-responsive"/>
                        {else}
                            <img src="{$img_cat_dir}{$category.id_category}medium_default.jpg" alt="{$category.name|escape:'html':'UTF-8'}" width="{$mediumSize.width}" height="{$mediumSize.height}" class="img-responsive"/>
                        {/if}
                    </a>
                    <h5>
                        <a class="product-name" href="{$link->getCategoryLink($category.id_category, $category.link_rewrite)|escape:'html':'UTF-8'}">
                            <strong>{$category.name|escape:'html':'UTF-8'}</strong>
                        </a>
                    </h5>
                </div>
            </li>
        {/foreach}
            </ul>
        </div>
{/if}

Save, upload, clear cache. Should work, In my shop works.

Few disclaimers:

In SearchController.php You can edit parameters for findCategories() function. You can set last parameter to true instead of false if You want to search in meta_keywords of categories.

You should also change first parameter of this function from $query to $original_query if You are from Poland or something, because Tools::replaceAccentedChars(urldecode($query)); is removing "ł" and it changes it "l" instead. 

You can change col-lg-3 to col-lg-2 if You want to have 6 thumbnails instead of 4.

Good luck, I won't support this code and any issues with it