Efficient communication across multiple processors for finite elements
The answer was staring me right in the face, I just wasn't paying attention, apparently. Instead of sending one integer and one real*8 at a time, I should have been sending all of them at once, as:

do n=0,numProcs-1
    if( my_id .eq. n ) then
        do i=0,numProcs-1
            if( i .ne. my_id ) then
                currProc=i
                call MPI_RECV( numNeeded,1,MPI_INTEGER,i,my_id*2, &amp; 
                               MPI_COMM_WORLD,status,ierr )

                allocate( currNeeded(numNeeded) )
                allocate( volsNeeded(numNeeded) )

                call MPI_RECV( currNeeded,numNeeded,MPI_INTEGER,currProc,my_id*2+1, &amp; 
                               MPI_COMM_WORLD,status,ierr )

                do j=1,numNeeded
                    volsNeeded(j)=myElements(elementGlobalToLocal(currNeeded(j)))%xsj
                enddo

                call MPI_SEND( volsNeeded,numNeeded,MPI_REAL8,currProc,my_id, &amp; 
                               MPI_COMM_WORLD,status,ierr )

                deallocate( currNeeded )
                deallocate( volsNeeded )
            endif
        enddo
    else
        call MPI_SEND( numElementsNeeded(n+1),1,MPI_INTEGER,n,n*2, &amp; 
                       MPI_COMM_WORLD,status,ierr )

        call MPI_SEND( elementsNeeded(n+1, 1:numElementsNeeded(n+1)), &amp; 
                       numElementsNeeded(n+1),MPI_INTEGER,n,n*2+1, &amp; 
                       MPI_COMM_WORLD,status,ierr )

        call MPI_RECV( myExternalXsj(currReceived:currReceived+numElementsNeeded(n+1)), &amp; 
                       numElementsNeeded(n+1),MPI_REAL8,n,n,MPI_COMM_WORLD,status,ierr )

        do j=1,numElementsNeeded(n+1)
            elementGlobalToLocal(elementsNeeded(n+1, j))=currReceived
            currReceived=currReceived+1
        enddo
    endif
enddo


Reducing the MPI call times drastically reduces the time spent in communication from (on 8 cores) roughly 269 seconds to roughly 13 seconds, a speedup by a factor of more than 20. This still doesn't change the problem of low scalability, though perhaps using non-blocking send/receive operations (with a barrier after the end of the loop to ensure all messages are received/sent) will do that.