There is an established trail that was developed with the same aim as the idea behind your question: the Haute Randonnée Pyrénéenne. It is about 800km long from coast to coast and wiki states 45 days for the average hiker. It is however very remote and I would not advise is without decent hiking experience in mountainous terrain. It is also unmarked and the navigation is rather tricky in places.
Easier options are the GR10 and GR11, which run more or less parallel to the HRP further to the north in France (GR10) and further to the south in Spain (GR11). Those are more accessible and marked, but stay serious undertakings to cover in a single trek. The distances are somewhere between 800 and 900km (depending on the source).
Many variations are possible for each of those three trails, including switching from trail to trail. There are plenty of guidebooks around and the links on each of the wiki pages will give you a good start.
If you are feeling very competitive you might even try to race the length of the GR10 next summer.
There are no legal or political issues with the Spanish-French border. As long as you are allowed into the Schengen zone, you are fine. If you want to cross into Andorra and your nationality requires a Schengen visa, you should be a bit more careful and make sure that you have a multiple entry Schengen visa (source). Thanks to phoog for that catch.
And if you really care a lot about the Spanish-French border, keep in mind that it consists of the three unconnected pieces: one on each side of Andorra and the border around Llívia.