As mentioned, you can easily do this with the query module. I've done something very similar, but you could pass the needed variables to an embed to get the prev/next category.

{exp:query sql=
    "SELECT 
        cat_url_title as prev_cat_url_title, 
        cat_name as prev_cat_title
    FROM exp_categories 
    WHERE cat_url_title < '{embed:current_cat_url_title}'
    AND group_id = '1'
    DESC LIMIT 1"
}
<a href="../{prev_cat_url_title}/">{prev_cat_title}</a>
{/exp:query}

And to get the next entry, just change the where clause:

WHERE cat_url_title > '{embed:current_cat_url_title}'

As mentioned, you can easily do this with the query module. I've done something very similar, but you could pass the needed variables to an embed to get the prev/next category.

[removed] see updated answer below

Update

Depending on how your categories are ordered (alphabetical or custom) & nested a few more variables are needed. You will need to use an add-on like GWcode Categories to get the necessary variables for a query, specifically cat_order, which GWcode gets.

Parent Template:

{exp:gwcode_categories
    cat_url_title="{segment_3}"
    limit="1"
}
    {embed="some/template" cat_url_title="{cat_url_title}" group_id="{cat_group_id}" parent_id="{parent_id}" cat_order="{cat_order}"}
{/exp:gwcode_categories}

Embded

{exp:query sql=
"SELECT  
    cat_url_title as prev_cat_url_title, 
    cat_name as prev_cat_title
FROM exp_categories  
WHERE cat_url_title <> '{embed:cat_url_title}'
AND parent_id = {embed:parent_id}
AND group_id = {embed:group_id}
AND cat_order = {emebd:cat_order} - 1
LIMIT 1"
}
<a href="../{prev_cat_url_title}/">{prev_cat_title}</a>
{/exp:query}

For next category, change the cat_order clause to:

AND cat_order = {emebd:cat_order} + 1