Using the Apex v() function can result in major performance issues, as illustrated below.
Every function call can cause this type of issue because of the cost of context switching, so it is something to always look out for.
In my case, I had a procedure with a cursor like this: cursor c1 is select * from ( -- Page items select p.page_id , p.item_name , apex_util.get_session_state(p.item_name) as session_value from apex_application_page_items p where p.application_id = v('APP_ID') ) where session_value is not null order by 1 nulls first , 2 This has worked fine for over a year on 4 different Apex 4.2 environments; the query takes less than a second.
After upgrading two of those to Apex 5.1, one of the Apex 5.1 environments took over 1500 seconds (!) to complete this query. The other one still performed well. No idea what the difference was between those 2 environments that caused this; database version, Apex version and the procedure were identical.

Solution: Defining a variable "v_app_id number := v('APP_ID')" and using that in the cursor instead of v('APP_ID') solved the problem.

Note 1: This only occurred with apex_application_page_items; a similar query with e.g. apex_application_items didn't have any issues.

Note 2: This only occurred when using v() in a subquery; rewriting it like this also solved it:cursor c1 is -- Page items select p.page_id , p.item_name , apex_util.get_session_state(p.item_name) as session_value from apex_application_page_items p where p.application_id = v('APP_ID') and apex_util.get_session_state(p.item_name) is not null order by 1 nulls first , 2
So while the cause is a bit unclear, the solution is quite simple: avoid v() whenever possible (always a good idea) and avoid using it in subqueries.