The first thing you need to do first is to create a third library that has all of the categories from both of the first two libraries in it. Let's assume for purposes of this discussion that it is Library 3.
You then need to create a search results page. The search results page will have a title something like "Search Results," and the following two lines in it:
Next, go to the search results page. When seen on its own (not as a result of a search), it will have a complete list of all your links. Ignore that, because no one will ever see it. Now view the source of that page. There will be a bit in it that will read something like this:
<form method="get" id="llsearch">
<input onfocus="this.value=''" value="Search..." name="searchll" id="searchll" type="text">
<input value="X" name="page_id" id="page_id" type="hidden">
<input value="Search" type="submit">
where the input value (X) for the page_id will be the number of your newly created page. Copy and paste all of that code into each of your two library pages, and save each page.
Voila! You will have a search form that will search all your links. When someone uses the form, it will take them to your newly created Search Results page. However, the list of all the links will not appear on that page when it is found through the search function. Instead, that page will have only a search box and the results of the search.