I have 2 mobile passes. I did not know the reservation of seats had an extra cost, and I cannot find the trips I am looking for. 

Without specifying when you plan to travel, it’s difficult to help.

You are probably looking to far in the future, to find routes for your travel wishes. Two or three months in advance, most should be online. Some rail companies are always late (like those in Spain or Italy).

For a lot of trains with reservations, there are alternatives without mandatory seat reservations.

So if you can share your travel plans, we can advise you properly. Interrail/Eurail is a great flexible product and usually good value for money. But figuring out train travel is difficult for people not used to taking trains/public transport in Europe.

It requires a bit more planning than taking a plane from A to B.

I am looking for the following trips in july and august: 

• Madrid - Valencia (I found trips) but did not know I had to pay extra to book a seat. 
• Valencia - Granada (no options)
• Granada - Malaga (no options)
• Paris - Barcelona (the reservation is too expensive)
• Barcelona - Madrid 

July and August are not to be found in the planners yet, it’s too far away. Spain is always late with sharing it’s schedules. If you want an indication of how to get from A to B, put in the planner but use a random date for next week. Schedules usually don’t change much.

Your routes are Spain heavy, this is one of the most difficult Eurail/Interrail countries, with lots of mandatory seat reservations. You’ll need to make your reservations in ticket offices at the stations (but these cannot sell out). Once you arrive in Spain, head to a train station and ticket office, and book all your reservations in once.

For Paris Barcelona there are alternatives. With a smaller reservation cost. Take a TGV from Paris to Perpignan. Seat reservation cost is 10 EUR, or 20 if you book a bit later if the advantageous prices are sold out. Take local trains to Barcelona, via the stations of Cerbère (Fr) or Portbou (Es). These local trains don’t require a seat reservation.

The domestic TGV’s are also not open for booking yet for July in August. Usually 3-4 months in advance they’re bookable.

Read this guide below carefully, to find cheaper ways to book seat reservations than via the Interrail/Eurail website.

For your planning, don’t rely on the planners of Interrail/Eurail. They are often wrong. Rely on the planners of the train company that operates your train.

Deutsche Bahn has a planner encompassing most of Europe: https://www.bahn.com/en

Spanish train hours, most are found here: https://www.renfe.com/es/es/viajar/informacion-util/horarios

RES In ES/Renfe CAN and DO sell out-very often in high season=summer, as trains do simply get fully booked, sometimes even days ahead-and for anyone, also if you just wanted to buy normal billete.

Vlc-Grnd and also moreorless Grn-Mlg simply has NO good trainlines, this will lead you a very roundabout way with many changes. It is also not a wise plan-just look at a map, as you do double some long sectors in/out of Andalucia. In ES-just as in AG the BUS also has very good coverage and is for these links the better ALT. Grn->MLg runs ev hour and more direct. However-since a week or 3-4 there ARE now 2 new AVant hi-speed direct trenes between the 2, since last yr the new hi-sp. normal gauge single track to Grnd opened.

You may also save a load of pesos by not using pass, but the new Iryo or OUIGO hi-speed trenes that compete with that state-burocracy named RENFE from MAD to Bcn and Vlc for now-with more lines to follow later. But then you have to book-just like cheap airplanes, long before and at times that do not suit you-and loose all money if not going. But NO extra for luggage-other as airlines.

Buenes viajes, porteno!

Granada-Málaga has a couple of daily AVANT services. Reservations only cost €4 on those. 

Valencia-Granada is a bit difficult, it would require either taking the Torre del Oro to Córdoba (€7 reservation fee I believe) and switching there to an AVANT to Granada (€4 reservation fee), or switching AVE in Madrid (2×€12).

If I understand it correctly your route is Barcelona-Madrid-Valencia-Granada-Málaga, in which case I would suggest switching to Barcelona-Valencia-Madrid-Granada-Málaga, as that you can do with all legs being direct trains. In total this amounts to about €35 in reservations.

The Paris-Barcelona TGV is indeed notoriously expensive to reserve at €35. You can save a bit as Brendan mentioned by going from Perpignan to Barcelona using local trains, but it does take more time and is certainly less comfortable.

For refunds you will have to reach out to customer service if you don't manage to do it from your account. Note that unless you bought plus passes are generally only 85% refundable, and passes bought during certain sales (such as the black friday sale) are not refundable. If you did buy Plus the pass is refundable but the plus fee is not.

Buses are a good option, except that many times they have restricitions with luggage. 

Be sure to also check how much a regular Paris-Barcelona ticket would cost you. On some dates in July and August they cost over €130 per person and up to €229, meaning a €35 reservation is a bargain (even including the cost of a travel day). The cheapest tickets for that route are currently €69 so about the same price if you include the cost of a travel day.

Flights will not be cheaper if you're planning to bring luggage.