FrameLayout vs RelativeLayout for overlays
A common rule of thumb when choosing layouts is to select the combination that results in the smallest number of nested layout views.
Specific to your question, RelativeLayout is larger and more capable than the much simpler FrameLayout. So for simple layouts, the latter is probably more efficient. But if using RelativeLayout and it's added positioning options allows you to implement your GUI in a smaller number of layout views, then that would likely be a better choice.
Here's a page that discusses some trade-offs and demonstrates some helpful tools to use when designing your layouts. It mostly talks about RelativeLayout and LinearLayout, but is also apropos to your choice between RelativeLayout and Framelayout. Just keep in mind that FrameLayout is an even simpler layout.
Edit (2017): For even more complicated layouts, you may be able to avoid nested layouts by using ConstraintLayout.